algorithms1SortingAlgorithms

1package pkg4algorithms;2 3/*4 * algorithms1SortingAlgorithms.java5 * ----------------------6 * Bubble, selection, insertion, merge, quick, heap, and counting sort.7 *8 *  Algorithm     Best      Avg       Worst     Space   Stable9 *  ---------     ----      ---       -----     -----   ------10 *  Bubble        O(n)      O(n^2)    O(n^2)    O(1)    yes11 *  Selection     O(n^2)    O(n^2)    O(n^2)    O(1)    no12 *  Insertion     O(n)      O(n^2)    O(n^2)    O(1)    yes13 *  Merge         O(nlogn)  O(nlogn)  O(nlogn)  O(n)    yes14 *  Quick         O(nlogn)  O(nlogn)  O(n^2)    O(logn) no15 *  Heap          O(nlogn)  O(nlogn)  O(nlogn)  O(1)    no16 *  Counting      O(n+k)    O(n+k)    O(n+k)    O(k)    yes  (k = value range)17 */18import java.util.Arrays;19 20public class algorithms1SortingAlgorithms {21 22    static void bubble(int[] a) {23        for (int i = 0; i < a.length - 1; i++) {24            boolean swapped = false;25            for (int j = 0; j < a.length - 1 - i; j++)26                if (a[j] > a[j + 1]) { swap(a, j, j + 1); swapped = true; }27            if (!swapped) break;   // already sorted -> early exit28        }29    }30 31    static void selection(int[] a) {32        for (int i = 0; i < a.length - 1; i++) {33            int min = i;34            for (int j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;35            swap(a, i, min);36        }37    }38 39    static void insertion(int[] a) {40        for (int i = 1; i < a.length; i++) {41            int key = a[i], j = i - 1;42            while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }43            a[j + 1] = key;44        }45    }46 47    static void mergeSort(int[] a, int l, int r) {48        if (l >= r) return;49        int m = (l + r) >>> 1;50        mergeSort(a, l, m);51        mergeSort(a, m + 1, r);52        int[] tmp = new int[r - l + 1];53        int i = l, j = m + 1, k = 0;54        while (i <= m && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];55        while (i <= m) tmp[k++] = a[i++];56        while (j <= r) tmp[k++] = a[j++];57        System.arraycopy(tmp, 0, a, l, tmp.length);58    }59 60    static void quickSort(int[] a, int lo, int hi) {61        if (lo >= hi) return;62        int p = partition(a, lo, hi);63        quickSort(a, lo, p - 1);64        quickSort(a, p + 1, hi);65    }66    static int partition(int[] a, int lo, int hi) {67        int pivot = a[hi], i = lo - 1;          // Lomuto partition68        for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(a, ++i, j);69        swap(a, i + 1, hi);70        return i + 1;71    }72 73    static void heapSort(int[] a) {74        int n = a.length;75        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);   // build max-heap76        for (int end = n - 1; end > 0; end--) {                   // repeatedly extract max77            swap(a, 0, end);78            siftDown(a, end, 0);79        }80    }81    static void siftDown(int[] a, int n, int i) {82        while (true) {83            int l = 2 * i + 1, r = 2 * i + 2, largest = i;84            if (l < n && a[l] > a[largest]) largest = l;85            if (r < n && a[r] > a[largest]) largest = r;86            if (largest == i) break;87            swap(a, i, largest); i = largest;88        }89    }90 91    /** Counting sort for non-negative integers in range [0, max]. */92    static void countingSort(int[] a, int max) {93        int[] count = new int[max + 1];94        for (int v : a) count[v]++;95        int i = 0;96        for (int v = 0; v <= max; v++)97            for (int c = 0; c < count[v]; c++)98                a[i++] = v;99    }100 101    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }102 103    public static void main(String[] args) {104        int[] base = {9, 3, 7, 1, 8, 2, 6, 5, 4};105        int[] b;106        b = base.clone(); bubble(b);        System.out.println("bubble:    " + Arrays.toString(b));107        b = base.clone(); selection(b);     System.out.println("selection: " + Arrays.toString(b));108        b = base.clone(); insertion(b);     System.out.println("insertion: " + Arrays.toString(b));109        b = base.clone(); mergeSort(b, 0, b.length - 1); System.out.println("merge:     " + Arrays.toString(b));110        b = base.clone(); quickSort(b, 0, b.length - 1); System.out.println("quick:     " + Arrays.toString(b));111        b = base.clone(); heapSort(b);      System.out.println("heap:      " + Arrays.toString(b));112        b = new int[]{4, 2, 2, 8, 3, 3, 1};113        countingSort(b, 8);                  System.out.println("counting:  " + Arrays.toString(b));114    }115}