Fast O(n) Integer Sorting Algorithm
Join the DZone community and get the full member experience.
Join For Freeyesterday i learned that there is an o(n) integer sort algorithm (i should have read this before in a basic algorithm book :-/).
now i wondered: is this necessary in real applications? e.g. somewhere in java? today i have taken the counting sort and i can argue: yes, you should use integer sort especially for large arrays!
and when in detail should you apply the fast integer sort? apply it if
- you have positive integer values to sort. the requirement ‘positive’ and ‘integer’ is necessary for the listed o(n) algorithm, but not if you implement your own possible better solution .
-
you have a limited interval for the integer values (preferable min and max=m should be known before you sort)
e.g. if you know the maximum integer number in your array will be m=10^7 then you should use the integer sort if the array length n is roughly greater than m/2500 = 40000. this linear equation should hold true (for some values), because quick sort is nearly independent of m and the time-offset for integer sort increases nearly linear with m as you can see in the graph
now take a look at the graph where y =time in seconds for 10 runs and x =array length:
conclusion
i would apply this sorting algorithm only for n>10^7 where the difference between quicksort and integer sort could lay in the range of seconds. the memory consumption was not measured but should be ~twice times higher for the fast integer sort.
java sourcecode
//class linearsort
public static void main(string[] args) {
// init jvm
new linearsort().start(1000, 10000, 10000);
new linearsort().start(1000, 10000, 10000);
// run performance comparison
for (int maxinteger = 1000; maxinteger < 100000000; maxinteger *= 3) {
for (int arrlength = 1000; arrlength < 100000000; arrlength *= 3) {
system.gc();
new linearsort().start(arrlength, maxinteger, 10);
}
}
}
private random rand = new random();
// stop watch for integer sort with *unknown* range. marked as lin in the plot
private simpletimer linearstopwatch = new simpletimer();</pre>
// stop watch for integer sort with known range. marked as lin' in the plot
private simpletimer linearknownstopwatch = new simpletimer();
private simpletimer qsortstopwatch = new simpletimer();
private void start(int arrlength, int maxinteger, int times) {
for (int count = 0; count < times; count++) {
int[] list1 = new int[arrlength];
for (int i = 0; i < arrlength; i++) {
// do only allow positive integers until the specified 'max'-value
list1[i] = math.abs(rand.nextint(maxinteger));
}
linearstopwatch.start();
linearsort.sort(list1);
linearstopwatch.pause();
int[] list2 = arrays.copyof(list1, arrlength);
qsortstopwatch.start();
arrays.sort(list2);
qsortstopwatch.pause();
list2 = arrays.copyof(list1, arrlength);
linearknownstopwatch.start();
linearsort.sort(list2, 0, maxinteger);
linearknownstopwatch.pause();
}
system.out.println(maxinteger + ";" + arrlength + ";" + linearstopwatch
+ ";" + linearknownstopwatch
+ ";" + qsortstopwatch); // + ";" + qsortliststopwatch);
}
static int[] sort(int[] array, int min, int max) {
//the range is useful to minmize the memory usage
//countintegers holds the number of each integer
int[] countintegers = new int[max - min + 1];
for (int i = 0; i < array.length; i++) {
countintegers[array[i] - min]++;
}
int insertposition = 0;
//fill array in sorted order
for (int i = min; i <= max; i++) {
for (int j = 0; j < countintegers[i - min]; j++) {
array[insertposition++] = i;
}
}
return array;
}
static int[] sort(int[] array) {
int min, max = min = array[0];
//determine the max and min in the array
for (int i = 1; i < array.length; i++) {
if (array[i] < min)
min = array[i];
if (array[i] > max)
max = array[i];
}
return sort(array, min, max);
}
//class simpletimer
private long laststart = -1;
private long time;
public void start() {
if (laststart != -1)
throw new illegalstateexception("call stop before!");
laststart = system.currenttimemillis();
}
public void pause() {
if (laststart < 0)
throw new illegalstateexception("call start before!");
time = time + (system.currenttimemillis() - laststart);
laststart = -1;
}
public string tostring() {
return time / 1000f + "";
}
Opinions expressed by DZone contributors are their own.
Trending
-
Exploring the Capabilities of eBPF
-
What Is JHipster?
-
Integration Architecture Guiding Principles, A Reference
-
Revolutionize JSON Parsing in Java With Manifold
Comments