'Counting sort iterating from start
I have seen other questions on SO asking why the last iteration in counting sort, where we place elements on the sorted array cannot start from the start. The reason is that that way the sort algorithm loses its stability.
But what if we reversed the count also? Instead of counting the no of elements present before a specific element, what if we count the no of elements present after that specific element? I have implemented it like the following.
public class TestCountSort {
public static void main(String[] args) {
Element[] arr=new Element[]{new Element("One",1),new Element("Three",2),new Element("Two",1)};
System.out.println("Array before - "+Arrays.toString(arr));
countSort(arr);
System.out.println("Array after - "+Arrays.toString(arr));
}
public static void countSort(Element[] arr){
int n=arr.length;
int max=arr[0].key;
int min=arr[0].key;
for(Element i:arr){
if(i.key>max){
max=i.key;
}
if(i.key<min){
min=i.key;
}
}
int range=max-min+1;
int[] count=new int[range];
Element[] sortedArray=new Element[n];
for(Element i:arr){
count[i.key-min]++;
}
for(int i=range-2;i>=0;i--){
count[i]=count[i]+count[i+1];
}
for(int i=0;i<n;i++){
sortedArray[n-count[arr[i].key-min]]=arr[i];
count[arr[i].key-min]--;
}
for(int i=0;i<n;i++){
arr[i]=sortedArray[i];
}
}
}
class Element{
private String name;
public int key;
public Element(String name, int key){
this.name=name;
this.key=key;
}
public String toString(){
return "{"+name+":"+key+"}";
}
}
Will this preserve the stability and provide sorting? Or is there something I am missing?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
