Sort2.java

/*
    Sort2.java
    CIS 260
    David Klick
    2/2/05

Demonstration of various sorting algorithms.

Useful sites to visit:

http://linux.wku.edu/~lamonml/algor/sort/sort.html
    http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
*/

import java.text.*;

public class Sort2 {
    public static void main(String[] args) {
        long startTime, elapsedTime;
        int array_size = 50000;
        final long RANGE = (long)Integer.MAX_VALUE - Integer.MIN_VALUE + 1;

if (args.length > 0) {
           try {
              array_size = Integer.parseInt(args[0]);
              if (array_size < 10) array_size = 10;
           } catch (Exception e) {
              // ignore errors
           }
        }
        System.out.println("Sorting an array of " + array_size + " ints");
        int[] work = new int[array_size];
        int[] hold = new int[array_size];

// create an array of random integers
        for (int i=0; i<hold.length; i++) {
            hold[i] = (int)(Math.random() * RANGE + Integer.MIN_VALUE);
        }

// copy holding array to working array and do bubble sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using bubble sort ");
        startTime = System.currentTimeMillis();
        bubbleSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- bubble sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do my sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using my sort ");
        startTime = System.currentTimeMillis();
        mySort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- my sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do Jermey Wold's sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using Jermey Wold's sort ");
        startTime = System.currentTimeMillis();
        woldSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- my sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do selection sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using selection sort ");
        startTime = System.currentTimeMillis();
        selectionSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- selection sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do insertion sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using insertion sort ");
        startTime = System.currentTimeMillis();
        insertionSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- insertion sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do shell sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using shell sort ");
        startTime = System.currentTimeMillis();
        shellSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- shell sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do merge sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using merge sort ");
        startTime = System.currentTimeMillis();
        mergeSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- merge sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do heap sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using heap sort ");
        startTime = System.currentTimeMillis();
        heapSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- heap sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do quick sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.print("Sorting work array using quick sort ");
        startTime = System.currentTimeMillis();
        quickSort(work);
        elapsedTime = System.currentTimeMillis() - startTime;
        if (!isSorted(work)) System.out.println("- quick sort failed!");
        else System.out.println("- elapsed time: " + elapsedTime + "ms");

// copy holding array to working array and do robsort
        if (array_size < 12) {
            copyArray(hold, work);
            if (isSorted(work)) System.out.println("Error: array sorted before sort");
            System.out.print("Sorting work array using robsort ");
            startTime = System.currentTimeMillis();
            robSort(work);
            elapsedTime = System.currentTimeMillis() - startTime;
            if (!isSorted(work)) System.out.println("- rob sort failed!");
            else System.out.println("- elapsed time: " + elapsedTime + "ms");
        }
    }
    public static void copyArray(int[] from, int[] to) {
        int max = from.length;
        if (max != to.length) {
            System.out.println("*** Warning: copyArray called with different length arrays ***");
            max = to.length;
        }
        for (int i=0; i<max; i++) to[i] = from[i];
    }

public static boolean isSorted(int[] a) {
        for (int i=0; i<a.length-1; i++) {
            if (a[i] > a[i+1]) return false;
        }
        return true;
    }

public static void mySort(int[] a) {
        int i, j, temp;
        int len = a.length;
        for (i=0; i<len-1; i++) {
            for (j = i+1; j<len; j++) {
                if (a[i] > a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

public static void bubbleSort(int[] a) {
        int i, j, temp;
        for (i=a.length-1; i>=0; i--) {
            for (j = 1; j <= i; j++) {
                if (a[j-1] > a[j]) {
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

public static void woldSort(int[] a) {
        int i, j, k, temp;
        for (i=0; i<a.length-1; i++) {
            for (j=i+1; j<a.length; j++) {
                if (a[i] > a[j]) {
                    temp = a[j];
                    for (k=j; k>i; k--) a[k] = a[k-1];
                    a[i] = temp;
                }
            }
        }
    }

public static void selectionSort(int[] a) {
        int i, j, min, temp;
        for (i=0; i<a.length-1; i++) {
            min = i;
            for (j=i+1; j<a.length; j++) {
                if (a[j] < a[min]) min = j;
            }
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

public static void insertionSort(int[] a) {
        int i, j, temp;
        for (i=1; i<a.length; i++) {
            temp = a[i];
            j = i;
            while ((j>0) && (a[j-1] > temp)) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = temp;
        }
    }

public static void shellSort(int[] a) {
        int i, j, incr, temp;
        incr = 3;
        while (incr > 0) {
            for (i=0; i<a.length; i++) {
                j = i;
                temp = a[i];
                while ((j >= incr) && (a[j-incr] > temp)) {
                    a[j] = a[j-incr];
                    j -= incr;
                }
                a[j] = temp;
            }
            if (incr/2 != 0) incr /= 2;
            else if (incr == 1) incr = 0;
            else incr = 1;
        }
    }

public static void mergeSort(int[] a) {
        int[] tmp = new int[a.length];
        m_sort(a, tmp, 0, a.length-1);
    }

private static void m_sort(int[] a, int[] tmp, int left, int right) {
        int mid;
        if (right > left) {
            mid = (right + left) / 2;
            m_sort(a, tmp, left, mid);
            m_sort(a, tmp, mid+1, right);
            merge(a, tmp, left, mid+1, right);
         }
    }

private static void merge(int[] a, int[] tmp, int left, int mid, int right) {
        int i, left_end, num_elements, tmp_pos;
        left_end = mid - 1;
        tmp_pos = left;
        num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right)) {
            if (a[left] <= a[mid]) tmp[tmp_pos++] = a[left++];
            else tmp[tmp_pos++] = a[mid++];
        }

while (left <= left_end) tmp[tmp_pos++] = a[left++];
        while (mid <= right) tmp[tmp_pos++] = a[mid++];

for (i=0; i < num_elements; i++) {
            a[right] = tmp[right];
            right--;
        }
    }

public static void heapSort(int[] a) {
        int len = a.length;
        for (int i=len/2; i>0; i--) siftDown(a, i, len);
        do {
            int tmp = a[0];
            a[0] = a[len-1];
            a[len-1] = tmp;
            len--;
            siftDown(a, 1, len);
        } while (len>1);
    }

private static void siftDown(int[] a, int k, int bottom) {
        int tmp = a[k-1];
        while (k <= bottom/2) {
            int j = k + k;
            if ((j < bottom) && (a[j-1]<a[j])) j++;
            if (tmp >= a[j-1]) break;
            else {
                a[k-1] = a[j-1];
                k = j;
            }
        }
        a[k-1] = tmp;
    }

public static void quickSort(int[] a) {
        q_sort(a, 0, a.length-1);
    }

private static void q_sort(int[] a, int left, int right) {
        int pivot, l_hold, r_hold;
        l_hold = left;
        r_hold = right;
        pivot = a[left];
        while (left < right) {
            while ((a[right] >= pivot) && (left < right)) right--;
            if (left != right) a[left++] = a[right];
            while ((a[left] <= pivot) && (left < right)) left++;
            if (left != right) a[right--] = a[left];
        }
        a[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot) q_sort(a, left, pivot-1);
        if (right > pivot) q_sort(a, pivot+1, right);
    }

private static void robSort(int[] a) {
        while (!isSorted(a)) {
            for (int i=0; i<a.length; i++) {
                int x  = (int) (Math.random() * a.length);
                int y = (int) (Math.random() * a.length);
                int temp = a[x];
                a[x] = a[y];
                a[y] = temp;
            }
        }
    }
}

/*
    Sample output:

Sorting an array of 50000 ints
    Sorting work array using bubble sort - elapsed time: 91070ms
    Sorting work array using my sort - elapsed time: 83100ms
    Sorting work array using Jermey Wold's sort - elapsed time: 70030ms
    Sorting work array using selection sort - elapsed time: 50480ms
    Sorting work array using insertion sort - elapsed time: 32350ms
    Sorting work array using shell sort - elapsed time: 14010ms
    Sorting work array using merge sort - elapsed time: 110ms
    Sorting work array using heap sort - elapsed time: 170ms
    Sorting work array using quick sort - elapsed time: 110ms
*/