I've written a program to compare different sorting algorithms with the array size being 10, 1,000, 100,000, 1,000,000 and 10,000,000. I, of course, expect Insertion to win out on 10 and merge heap and quick to really perform at the upper levels.
However, below are the times I'm getting. (Note that quick sort is growing much faster than heap and merge even though they are all \$\theta(n \log n)\$.)
Things I've considered:
- Each algorithm uses the same seed to initialize each array, so the numbers are the same.
- I am only timing the algorithm and nothing extra.
- My professor approves of the code and doesn't know what's wrong, but maybe we're both missing something.
- I moved the program from my flash drive to the desktop to test possible data transfer problems.
- The algorithm (except for test 2) has only run at night with nothing else going.
Key: Hours:Minutes:Seconds:Milliseconds:Microseconds
Test 3
n Insertion Merge Heap Quick 10 0:0:0:0:3 0:0:0:0:28 0:0:0:0:35 0:0:0:0:43 1000 0:0:0:11:470 0:0:0:2:358 0:0:0:7:787 0:0:0:3:596 100000 0:0:1:911:865 0:0:0:51:506 0:0:0:24:257 0:0:0:55:519 1000000 0:3:59:769:105 0:0:0:351:129 0:0:0:238:878 0:0:0:916:885 10000000 8:11:44:552:820 0:0:3:521:108 0:0:3:560:178 0:1:13:709:830
Test 2
n Insertion Merge Heap Quick 10 0:0:0:0:5 0:0:0:0:49 0:0:0:0:37 0:0:0:0:50 1000 0:0:0:15:473 0:0:0:2:893 0:0:0:8:402 0:0:0:5:230 100000 0:0:2:518:566 0:0:0:57:845 0:0:0:32:917 0:0:0:71:243 1000000 0:5:38:538:795 0:0:0:460:796 0:0:0:312:66 0:0:1:398:508 10000000 11:48:6:630:6390:0:3:690:329 0:0:3:518:281 0:1:18:180:11
Test 1
n Insertion Merge Heap Quick 10 2676ns 19626ns 26316ns 33454ns 1000 11504040ns 2298935ns 6835250ns 3741456ns 100000 1849274815ns 47654052ns 23620952ns 52819295ns 1000000 0:3:58ns 0:0:0ns 0:0:0ns 0:0:0ns 10000000 8:10:25ns 0:0:3ns 0:0:3ns 0:1:15ns
Here's my quick sort implementation (35 lines):
public static long quick(int[] list) {
long startTime = System.nanoTime();
quickSort(list, 0, list.length - 1);
long endTime = System.nanoTime();
return endTime - startTime;
}
public static void quickSort(int[] A, int p, int r) {
if(p < r) {
int q = randomizedPartition(A, p, r);
quickSort(A, p, q-1);
quickSort(A, q+1, r);
}
}
public static int randomizedPartition(int[] A, int p, int r) {
Random random = new Random();
int i = random.nextInt((r-p)+1)+p;
swap(A,r,i);
return partition(A,p,r);
}
public static int partition(int[] A, int p, int r) {
int x = A[r];
int i = p-1;
for(int j = p; j < r; j++) {
if(A[j] <= x) {
i++;
swap(A, i, j);
}
}
swap(A, i+1, r);
return i+1;
}
And if needed (267 lines) here's my entire code:
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.io.*;
public class algComp {
public static void main(String[] args) {
driver(10); // Sort array of length 10
driver(1_000); // Sort array of length 1000
driver(100_000);
/* WARNING: Running program with the below values takes a lot of time!! */
driver(1_000_000);
//driver(10_000_000);
/* You are now leaving the danger zone. */
System.out.println("-----------------------------------------------");
content = String.format(content + "\nKey: Hours:Minutes:Seconds:Milliseconds:Microseconds");
printToFile(); // Prints data to times.txt
}
public static void driver(int n) {
// Insertion sort
int[] list = data(n);
if(n == 10) {
System.out.format("%10s","Unsorted: ");
printList(list);
}
long iTime = insertion(list);
if(n == 10) {
System.out.format("%10s","iSorted: ");
printList(list);
}
// Merge sort
list = data(n);
long mTime = mergeSort(list);
if(n == 10) {
System.out.format("%10s","mSorted: ");
printList(list);
}
// Heap sort
list=data(n);
long hTime = heap(list);
if(n == 10) {
System.out.format("%10s","hSorted: ");
printList(list);
}
// Quick sort
list=data(n);
long qTime = quick(list);
if(n == 10) {
System.out.format("%10s","qSorted: ");
printList(list);
}
if(n == 10) { // This will only print once
// Print prettifying stuff
System.out.println("Data is being written to times.txt...");
content = String.format(content + "%-9s%-17s%-17s%-17s%-17s\n",
"n","Insertion","Merge","Heap","Quick");
}
content = String.format(content + "%-9d%-17s%-17s%-17s%-17s%-1s",n,displayTime(iTime),
displayTime(mTime),displayTime(hTime),displayTime(qTime),"\n");
}
public static long insertion(int[] A) {
long startTime = System.nanoTime();
int i, j, key;
for(j = 1; j < A.length; j++) {
key = A[j];
// If previous is greater than selected (key) swap
for(i = j - 1; (i >= 0) && (A[i] > key); i--) {
A[i+1] = A[i];
}
A[i+1] = key;
}
long endTime = System.nanoTime();
return endTime - startTime;
}
public static long mergeSort(int[] A) {
long startTime = System.nanoTime();
if(A.length > 1) {
// First Half
int[] firstHalf = new int[A.length/2];
System.arraycopy(A, 0, firstHalf, 0, A.length/2);
mergeSort(firstHalf);
// Second Half
int secondHalfLength = A.length - A.length/2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(A, A.length/2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge two arrays
merge(firstHalf,secondHalf,A);
}
long endTime = System.nanoTime();
return endTime - startTime;
}
public static void merge(int[] A1, int[] A2, int[] temp) {
int current1 = 0; // Current index in list 1
int current2 = 0; // Current index in list 2
int current3 = 0; // Current index in temp
// Compares elemets in A1 and A2 and sorts them
while(current1 < A1.length && current2 < A2.length) {
if(A1[current1] < A2[current2])
temp[current3++] = A1[current1++];
else
temp[current3++] = A2[current2++];
}
// Merge two arrays into temp
while(current1 < A1.length)
temp[current3++] = A1[current1++];
while(current2 < A2.length)
temp[current3++] = A2[current2++];
}
public static long heap(int[] A) {
long startTime = System.nanoTime();
int temp;
int heapSize = A.length-1;
buildMaxHeap(A);
for(int i = A.length-1; i >= 1; i--) {
swap(A,0,i); // Root is now biggest element, swap to end of array
heapSize--; // Reduce heapSize to ignore sorted elements
maxHeapify(A,0,heapSize);
}
long endTime = System.nanoTime();
return endTime - startTime;
}
public static void buildMaxHeap(int[] A) {
int heapSize = A.length-1;
// Bottom up, check parents children, sort and move up tree
for(int i = (heapSize/2); i >= 0; i--)
maxHeapify(A,i,heapSize);
}
public static void maxHeapify(int[] A, int i, int heapSize) {
int temp,largest;
int l = left(i); // 2i
int r = right(i); // 2i + 1
if(l <= heapSize && A[l] > A[i]) // Check left child (which is largest?)
largest = l;
else largest = i;
if(r <= heapSize && A[r] > A[largest]) // Check right child
largest = r;
if(largest != i) { // If parent is biggest do nothing, else make parent largest
swap(A,i,largest);
maxHeapify(A,largest,heapSize);
}
}
public static int left(int i) {
return 2*i;
}
public static int right(int i) {
return 2*i+1;
}
public static long quick(int[] list) {
long startTime = System.nanoTime();
quickSort(list, 0, list.length - 1);
long endTime = System.nanoTime();
return endTime - startTime;
}
public static void quickSort(int[] A, int p, int r) {
if(p < r) {
int q = randomizedPartition(A, p, r);
quickSort(A, p, q-1);
quickSort(A, q+1, r);
}
}
public static int randomizedPartition(int[] A, int p, int r) {
Random random = new Random();
int i = random.nextInt((r-p)+1)+p;
swap(A,r,i);
return partition(A,p,r);
}
public static int partition(int[] A, int p, int r) {
int x = A[r];
int i = p-1;
for(int j = p; j < r; j++) {
if(A[j] <= x) {
i++;
swap(A, i, j);
}
}
swap(A, i+1, r);
return i+1;
}
public static void swap(int[] list, int i, int j) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
public static String displayTime(long n) {
long hours = TimeUnit.NANOSECONDS.toHours(n);
long minutes = TimeUnit.NANOSECONDS.toMinutes(n) - (TimeUnit.NANOSECONDS.toHours(n)*60);
long seconds = TimeUnit.NANOSECONDS.toSeconds(n) - (TimeUnit.NANOSECONDS.toMinutes(n) *60);
long milliseconds = TimeUnit.NANOSECONDS.toMillis(n) - (TimeUnit.NANOSECONDS.toSeconds(n)*1000);
long microseconds = TimeUnit.NANOSECONDS.toMicros(n) - (TimeUnit.NANOSECONDS.toMillis(n)*1000);
String displayThis = (hours + ":" + minutes + ":" + seconds + ":" + milliseconds + ":" + microseconds);
return displayThis;
}
public static int[] data(int n) {
Random random = new Random(seed); // Random seed stays same for all sorts
int[] list = new int[n];
for(int i = 0; i < list.length; i++) {
list[i] = random.nextInt(1000);
}
return list;
}
public static void printList(int[] list) {
for(int i = 0; i < list.length; i++) {
System.out.format("%5d",list[i]);
}
System.out.println();
}
public static void printToFile() {
// Print to file
try {
File file = new File("times.txt");
if(!file.exists())
file.createNewFile();
FileWriter fw = new FileWriter(file.getAbsoluteFile());
BufferedWriter bw = new BufferedWriter(fw);
bw.write(content);
bw.close();
System.out.println("Done.");
} catch (IOException e) {
e.printStackTrace();
}
}
// Global variables
public static String content = ""; // Used to print data to text file times.txt
public static int seed = (int)(Math.random()*10_000); // Seed for generating lists
}
What do you think? Surely quick sort should be running near 3 seconds at 10mil rather than a minute. What am I doing wrong?
