Sorting Algorithms

insertion sort image

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%-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 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

Back to top ▴