Compression Technique to sort 10,000 integers in an array ranging from 1-10.
This is a favorite coding interview question in sorting and searching algorithm optimization.
One can solve this using Merge Sort which gives O(nlog n) complexity. But is there any way to implement with reduced complexity?
Well I tried to figure out a way using Java's HashMap.
Also there are specific sorts available to sort the numbers in linear time complexity:
Code Implementation :
package com.practice.algorithms;
import java.util.Map.Entry;
import java.util.Random;
//import java.util.TreeMap;
import java.util.HashMap;
public class HashMapSortTest {
public static void main(String[] args) {
int size = 10000;
int[] array = new int[size];
//TreeMap<Integer, Integer> sorted = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> sorted = new HashMap<Integer, Integer>();
double startTime = System.nanoTime();
for(int i=0; i<array.length; i++){
Random random = new Random();
array[i] = random.nextInt(10-1+1) + 1;
switch(array[i]){
case 1:
if(sorted.containsKey(1)){
int count = sorted.get(1);
sorted.remove(1);
sorted.put(1, count+1);
}
else{
sorted.put(1, 1);
}
break;
case 2:
if(sorted.containsKey(2)){
int count = sorted.get(2);
sorted.remove(2);
sorted.put(2, count+1);
}
else{
sorted.put(2, 1);
}
break;
case 3:
if(sorted.containsKey(3)){
int count = sorted.get(3);
sorted.remove(3);
sorted.put(3, count+1);
}
else{
sorted.put(3, 1);
}
break;
case 4:
if(sorted.containsKey(4)){
int count = sorted.get(4);
sorted.remove(4);
sorted.put(4, count+1);
}
else{
sorted.put(4, 1);
}
break;
case 5:
if(sorted.containsKey(5)){
int count = sorted.get(5);
sorted.remove(5);
sorted.put(5, count+1);
}
else{
sorted.put(5, 1);
}
break;
case 6:
if(sorted.containsKey(6)){
int count = sorted.get(6);
sorted.remove(6);
sorted.put(6, count+1);
}
else{
sorted.put(6, 1);
}
break;
case 7:
if(sorted.containsKey(7)){
int count = sorted.get(7);
sorted.remove(7);
sorted.put(7, count+1);
}
else{
sorted.put(7, 1);
}
break;
case 8:
if(sorted.containsKey(8)){
int count = sorted.get(8);
sorted.remove(8);
sorted.put(8, count+1);
}
else{
sorted.put(8, 1);
}
break;
case 9:
if(sorted.containsKey(9)){
int count = sorted.get(9);
sorted.remove(9);
sorted.put(9, count+1);
}
else{
sorted.put(9, 1);
}
break;
case 10:
if(sorted.containsKey(10)){
int count = sorted.get(10);
sorted.remove(10);
sorted.put(10, count+1);
}
else{
sorted.put(10, 1);
}
break;
}
}
int[] sortedArray = new int[size];
int current = 0;
for(Entry<Integer, Integer> entry : sorted.entrySet()){
int key = entry.getKey();
int value = entry.getValue();
//System.out.println(key+" "+value);
value=current+value;
for(int i=current; i<value; i++){
sortedArray[i] = key;
}
current=value;
}
double timeElapsed = System.nanoTime()-startTime;
System.out.println("Execution Time : "+timeElapsed/1000000000+"s");
for(int k:sortedArray){
System.out.print(k+" ");
}
}
}
