Cognitame

'Does that hurt? Yeeaahh. Get it. That's just stimuli, you're reacting to it. You get used to that. Pain, you can get used to pain. You can adjust to it. You can adjust to pretty much anything. Just as long as there's routine. Right? Routine. The human mind craves it. Needs it. But if you take that away, that... that's when you start to lose your shit.' -Frank Castle

Sorting Algorithms

by Ethan Glover, Fri, Oct 24, 2014 - (Edited) Fri, Oct 24, 2014

Algorithm Comparison Program

Below is a program that utilizes and compares the times of Insertion Sort, Merge Sort, Heap Sort and QuickSort. I found it interesting that while this randomized version of QuickSort is obviously much faster with large data and generally more stable with random data, that it is very easy to slow it down.

QuickSort is the same as Heap and Merge in that it is Theta(nlgn). However, it differs from those two in that it is O(n^2) while Heap and Merge remain at O(nlgn) at the worst case scenario. QuickSort’s weakness comes especially when you attempt to sort already sorted data. This causes the program to have to “dig very deeply” with its recursion.

In fact, when I used QuickSort originally with 10 million integers in a range of 1 to 1000 it took more than a minute to sort while the others generally took 3 seconds. This happens because within that data there are many repeated elements and the algorithm is more likely to run into that sorted data problem. If you were to fill the array to be sorted full of the same integer (0 for example) the program will inevitably return a stack overflow error.

The idea of randomized QuickSort is of course to avoid then^2 problem in the first place, but keep in mind that with large data and a very small range of numbers, this won’t necessarily help.

So, while QuickSort can be much faster, there are always tradeoffs. It seems that with some extreme data that is nearly sorted, or contains many repeating elements, it is probably better to go with Heap sort which I found to be barely faster than Merge with large data.

Algorithm Comparison Program

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%-17sn",
"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 elements 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) {
int i = p + (int)(Math.random() *((r-p)+1)); // Random number between p-r
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(list.length);
}

return list;
}

public static void printList(int[] list) {
for(int i = 0; i < list.length; i++) {
System.out.format("%3d",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
}