'They seemed to think that the greatness of their masters was transferable to themselves. It was considered as being bad enough to be a slave; but to be a poor man's slave was deemed a disgrace indeed!' -Frederick Douglass, Narrative of the Life of Frederick Douglass

Sorting Algorithms

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

Table of Contents

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
}
Back to Top