Up to date

class HeapSortDescendingOrder { private static Comparable[] array; private static int count; private HeapSortDescendingOrder() { } public static void sort(Comparable[] list) { // assign list to array so it can be used in private methods without passing to method parameter array = list; count = list.length; // Build min heap for(int i = array.length/2; i >= 0; i--) { sink(i); } // shift each element at sorted position while(count > 0) { // put 0th element in it's sorted positon swap(0, --count); // maintain heap property sink(0); } } private static void sink(int root) { int child = getLeftChildIndex(root); while(child <= count-1) { // if there is right child. Right chlild = Left child + 1 if(child < count-1 && greater(array[child

class HeapSortAscendingOrder { private static Comparable[] array; private static int count; private HeapSortAscendingOrder() { } public static void sort(Comparable[] list) { // assign list to array so it can be used in private methods without passing to method parameter array = list; count = list.length; // Build max heap for(int i = array.length/2; i >= 0; i--) { sink(i); } // shift each element at sorted position while(count > 0) { // put 0th element in it's sorted positon swap(0, --count); // maintain heap property sink(0); } } private static void sink(int root) { int child = getLeftChildIndex(root); while(child <= count-1) { // if there is right child. Right chlild = Left child + 1 if(child < count-1 && less(array[child], ar

class MaxPriorityQueue > { private Key[] queue; private int count; private static final int CAPACITY = 3; public MaxPriorityQueue() { this(CAPACITY); } public MaxPriorityQueue(int capacity) { queue = (Key[]) new Comparable[capacity]; count = 0; } public boolean isEmpty() { return count == 0; } public void insert(Key key) { // validate size and resize queue is needed if(queue.length == count) { resize(2*queue.length); } // add key after last eleent in queue queue[count++] = key; // maintain binary heap property swim(count-1); } public Key deleteMin() { Key min = queue[0]; // For sorting swap it with last element // assign last element to root queue[0] = queue[--count]; // free last space queue[count] = null; // maintain binary heap property sink

class MinPriorityQueue > { private Key[] queue; private int count; private static final int CAPACITY = 3; public MinPriorityQueue() { this(CAPACITY); } public MinPriorityQueue(int capacity) { queue = (Key[]) new Comparable[capacity]; count = 0; } public boolean isEmpty() { return count == 0; } public void insert(Key key) { // validate size and resize queue is needed if(queue.length == count) { resize(2*queue.length); } // add key after last eleent in queue queue[count++] = key; // maintain binary heap property swim(count-1); } public Key deleteMin() { Key min = queue[0]; // For sorting swap it with last element // assign last element to root queue[0] = queue[--count]; // free last space queue[count] = null; // maintain binary heap property sink

What is heap data structure? Heap is complete binary tree that satisfy either min-heap or max-heap condition. Max Heap : Every element must be >= all descendent elements. Min Heap : Every element must be <= all descendent elements. In 1, 2, 3.... based indexing Root = array[index] Parent = array[index/2] Left Node = array[2 * index] Right Node = array[2 * index + 1] In 0, 1, 2, 3.... based indexing, Good Read Root = array[index] Parent = array[(index-1)/2] Left Node = array[2 * index + 1] Right Node = array[2 * index + 2] Heap implementations :  1. Priority Queue : A.  Min ,  B.  Max 2. Heap Sort : Ascending order , Descending order

Shellsort: which increment sequence to use? Powers of two. 1, 2, 4, 8, 16, 32, ... No. Powers of two minus one. 1, 3, 7, 15, 31, 63, … Maybe. 3x + 1. 1, 4, 13, 40, 121, 364, … OK. Easy to compute. class ShellSort { public static void sort(int[] array) { int N = array.length; int h = 1; while(h < N/3) { // 3h +1 sequence h = 3*h+1; // 1, 4, 13, 40, 121, 364, ... } while(h >=1) { // h-sort the array. // insertion sort for(int i = h; i < N; i++) { for(int j = i; j >= h && less(array[j], array[j-h]); j -= h) { swap(array, j, j-h); } } h = h/3; // move to next increment } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private static boolean less(int key

Read 1

class CountSort { public static void sort(int[] array) { // Find largest element int max = Integer.MIN_VALUE; for(int element : array) { if(less(max, element)) { max = element; } } // Create an array with largest element int[] frequency = new int[max+1]; // count all element occurances in frequency array for(int element : array) { frequency[element]++; } int j = 0; // Iterate frequency array from left to right and copy into array for(int i = 0; i < frequency.length; i++) { // if frequency[i] > 0 then element exist in array so copy back in the order while(frequency[i] > 0) { array[j++] = i; frequency[i]--; } } } private static boolean less(int key1, int key2) { return key1 < key2; } pri

class MergeSort { public static void sort(int[] array) { // auxilary array of size O(n) used by merge process int[] aux = new int[array.length]; int N = array.length; for (int sz = 1; sz < N; sz = 2*sz) { for (int low = 0; low < N-sz; low = low + 2*sz) { int high = Math.min(low + 2*sz-1, N-1); int mid = low+sz-1; merge(array, aux, low, mid, high); } } } private static void merge(int[] array, int[] aux, int low, int mid, int high) { // copy from array to aux int i = low; for(; i <= high; i++) { aux[i] = array[i]; } // merge aux to array i = low; // used for first sub array int j = mid+1; // used for second sub array int k = low; // used for merged array while(k <= high) { if(i > mid) { array[k++] = aux[

class MergeSort { public static void sort(int[] array) { // auxilary array of size O(n) used by merge process int[] aux = new int[array.length]; ///////////////////////////////// // Improvement 3 : Initialize aux only once for(int i = 0; i < array.length; i++) { aux[i] = array[i]; } ////////////////////////////// sort(aux, array, 0, array.length-1); } private static void sort(int[] array, int[] aux, int low, int high) { if(high <= low) { return; // sorting not required } int mid = low + (high-low)/2; ///////////////////////// // Improvement 3 : switch role of aux and array in each sort call sort(aux, array, low, mid); sort(aux, array, mid+1, high); //////////////////////////// merge(array, aux, low, mid, high); } private static void merge(int[] array, int[] aux, int low, int mid, in

class MergeSort { public static void sort(int[] array) { // auxilary array of size O(n) used by merge process int[] aux = new int[array.length]; sort(array, aux, 0, array.length-1); } private static void sort(int[] array, int[] aux, int low, int high) { if(high <= low) { return; // sorting not required } int mid = low + (high-low)/2; sort(array, aux, low, mid); sort(array, aux, mid+1, high); // Improvement 2 : if(less(array[mid], array[mid+1])) { // both sub arrays are already Unsorted // so skip merge return; } merge(array, aux, low, mid, high); } private static void merge(int[] array, int[] aux, int low, int mid, int high) { // copy from array to aux int i = low; for(; i <= high; i++) { aux[i] = array[i]; } // merge aux to array i = l

class MergeSort { // use CUTOFF to sort small sub array // CUTOFF can be taken 7 to 10 items private static final int CUTOFF = 4; public static void sort(int[] array) { // auxilary array of size O(n) used by merge process int[] aux = new int[array.length]; sort(array, aux, 0, array.length-1); } private static void sort(int[] array, int[] aux, int low, int high) { // Improvement 1 :: // Using insertion sort for small sub array // For first pass skip the InsertionSort if(high <= low + CUTOFF - 1) { InsertionSort.sort(array, low, high); return; // sorting not required } int mid = low + (high-low)/2; sort(array, aux, low, mid); sort(array, aux, mid+1, high); merge(array, aux, low, mid, high); } private static void merge(int[] array, int[] aux, int low, int mid, int high) { // copy from array to aux int i

class MergeSort { public static void sort(int[] array) { // auxilary array of size O(n) used by merge process int[] aux = new int[array.length]; sort(array, aux, 0, array.length-1); } private static void sort(int[] array, int[] aux, int low, int high) { if(high <= low) { return; // sorting not required } int mid = low + (high-low)/2; sort(array, aux, low, mid); sort(array, aux, mid+1, high); merge(array, aux, low, mid, high); } private static void merge(int[] array, int[] aux, int low, int mid, int high) { // copy from array to aux int i = low; for(; i <= high; i++) { aux[i] = array[i]; } // merge aux to array i = low; // used for first sub array int j = mid+1; // used for second sub array int k = low; // used for merged array while(k <= high) { if(i >

  Recursive Java program Iterative Java program (Bottom up) Improvements 1. Use insertion sort for small subarrays : Mergesort has too much overhead for tiny subarrays. Cutoff to insertion sort for ≈ 7 items. Java program 2. Stop if already sorted : Is biggest item in first half ≤ smallest item in second half? Helps for partially-ordered arrays.  Java program 3. Eliminate the copy to the auxiliary array :  Save time (but not space) by switching the role of the input and auxiliary array in each recursive call. Java program

class ThreeWayQuickSort { public static void sort(int[] array) { sort(array, 0, array.length-1); } private static void sort(int[] array, int low, int high) { if(high <= low) { return; } // 3-way partition int v = array[low]; int lt = low; int gt = high; int i = low; while(i <= gt) { if(array[i] < v) { swap(array, i++, lt++); } else if (array[i] > v) { swap(array, i, gt--); } else { i++; } } sort(array, low, lt-1); sort(array, gt+1, high); } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private static void display(int[] array) { for(int key : array) { System.out.print(key + " "); } }

private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int m = medianOf3(a, lo, lo + (hi - lo)/2, hi); swap(a, lo, m); int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); }

class QuickSort { // CUTOFF to use insertion sort intead of quick sort for sub array private static final int CUTOFF = 5; public static void sort(int[] array) { sort(array, 0, array.length-1); } private static void sort(int[] array, int low, int high) { // -1 to allow fist pass to use quick sort if(high <= low + CUTOFF - 1) { // improvement : use insertion sort for small sub array InsertionSort.sort(array, low, high); return; } int j = partition(array, low, high); sort(array, low, j-1); sort(array, j+1, high); } private static int partition(int[] array, int low, int high) { int i = low; int j = high+1; // find item on left to swap while(true) { while(less(array[++i], array[low])) { if(i == high) { // corner case : avoid ArrayIndexOutOfBoundsException break; }

import java.util.Random; import java.util.concurrent.ThreadLocalRandom; class QuickSort { public static void sort(int[] array) { // improvement :: shuffle needed for performance guarantee shuffleArray(array); sort(array, 0, array.length-1); } private static void sort(int[] array, int low, int high) { if(high <= low) { // corner case return; } int j = partition(array, low, high); sort(array, low, j-1); sort(array, j+1, high); } // Implementing Fisher–Yates shuffle static void shuffleArray(int[] array) { // If running on Java 6 or older, use `new Random()` on RHS here Random random = ThreadLocalRandom.current(); for (int i = array.length - 1; i > 0; i--) { int index = random.nextInt(i + 1); // Simple swap swap(array, i, index); } } private static int partition(int[] array, int

class QuickSort { public static void sort(int[] array) { sort(array, 0, array.length-1); } private static void sort(int[] array, int low, int high) { if(high <= low) { // corner case return; } int j = partition(array, low, high); sort(array, low, j-1); sort(array, j+1, high); } private static int partition(int[] array, int low, int high) { int i = low; int j = high+1; // find item on left to swap while(true) { while(less(array[++i], array[low])) { if(i == high) { // corner case : avoid ArrayIndexOutOfBoundsException break; } } // find item on right to swap while(less(array[low], array[--j])) { if(j == low) { // corner case : avoid ArrayIndexOutOfBoundsException break; } }

If list is sorted ascending or descending order, time complexity of quick sort will be O(N^2) In Java used to sort primitive types. Quick Sort Basic program Improvements 1. Shuffle the input before sort : If array is already sorted in ascending or descending order then the worst case time complexity will be O(N^2). Can can avoid it by shuffling the array before sort. It will guarantee that worst case never happen and always time complexity will be NLogN. Java program 2. Use Insertion sort for small sub array : Quick and merge sorts are good for big array. Even quick sort has too much overhead for tiny subarrays. Cutoff to insertion sort for ≈ 10 items. ・Note: could delay insertion sort until one pass at end. Java program 3. Median of sample : Best choice of pivot item = median. Estimate true median by taking median of sample. Java Program 4. 3-Way partitioning : Quick sort with duplicate keys, Algorithm goes quadratic unless partitioning stops on equal keys! Put all items equal to

class SelectionSort { private static int[] array; private void sort() { for(int i = 0; i < array.length; i++) { int minIndex = i; for(int j = i+1; j < array.length; j++) { if(less(j, minIndex)) { minIndex = j; } } swap(i, minIndex); } } private void swap(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private boolean less(int i, int j) { return array[i] < array[j]; } private void display() { for(int key : array) { System.out.print(key + " "); } } public static void main (String[] args) { SelectionSort obj = new SelectionSort(); array = new int[] {11,13,7,12,16,9,24,5,10,3}; System.out.println("Unsorted array : "); obj.display(); obj.sort(); System.out.println("\nSorte

class InsertionSort { private static int[] array; private void sort() { for(int i = 1; i < array.length; i++) { for(int j = i; j > 0 && less(j, j-1); j--) { swap(j, j-1); } } } private void swap(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private boolean less(int i, int j) { return array[i] < array[j]; } private void display() { for(int key : array) { System.out.print(key + " "); } } public static void main (String[] args) { InsertionSort obj = new InsertionSort(); array = new int[] {11,13,7,12,16,9,24,5,10,3}; System.out.println("Unsorted array : "); obj.display(); obj.sort(); System.out.println("\nSorted array : "); obj.display(); } } Output Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7

class BubbleSort { private static int[] array; private void sort() { boolean sorted = true; for(int i = 0; i < array.length; i++) { for(int j = 1; j < array.length - i; j++) { if(array[j] < array[j-1]) { swap(j, j-1); sorted = false; } } if(sorted) { break; } } } private void swap(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private void display() { for(int key : array) { System.out.print(key + " "); } } public static void main (String[] args) { BubbleSort obj = new BubbleSort(); array = new int[] {11,13,7,12,16,9,24,5,10,3}; System.out.println("Unsorted array : "); obj.display(); obj.sort(); System.out.println("\nSorted array : "); obj.di

Criteria of Analysis : 1. Number of comparisons 2. Number of swaps  3. Stable 4. In-place 5. Memory used Comparison based sorts : 1. Bubble Sort - Code Can get kth largest element 2. Insertion Sort - Code 3. Selection Sort - Code Number of swaps O(n) Can get kth smallest element 4. Heap Sort          A scending order         Descending order         Additional Note: shiftDown take O(n) time over shiftUp O(nlogn). Ref1 , Ref2 . 5. Merge Sort 6. Quick Sort 7. Tree Sort 8. Shell Sort Index based sorts : 9. Count Sort :  Index based sorting. Fastest, Consume a lot of memory. The biggest advantage of counting sort is its complexity –  , where   is the size of the sorted array and   is the size of the helper array (range of distinct values). It has also several disadvantages – if non-primitive (object) elements are sorted, another helper array is needed to store the sorted elements. Second and the major disadvantage is that counting sort can be used only to sort discrete values (for examp

 A sorting algorithm is in-place if it uses ≤ c log N extra memory. A stable sort preserves the relative order of items with equal keys.

Ref: StackOverflow As for  Arrays.sort , Oracle implementation works as follows: For  int ,  long ,  float  and  double  there are essentially three algorithms: Insertion Sort, Dual-Pivot Stable Quicksort and Merge Sort. 1.1. If the array is large enough (currently larger than 286 elements)  and  it's not “almost sorted” (determined dynamically),  then  Merge Sort is used. 1.2. Otherwise, if the array is very small (currently less than 47 elements), then Insertion Sort is used. 1.3. Otherwise (if the array is not that small, but either smaller than 286 elements or mostly sorted), Dual-Pivot Quicksort is used. For  short  and  char , there are Insertion Sort, Dual-Pivot Stable Quicksort and Counting Sort. 2.1. If the array is larger than a certain threshold (currently 3200 elements), then Counting Sort is used. 2.2. Otherwise, similarly to larger types, Insertion Sort or Dual-Pivot Stable Quicksort is used (using the threshold of 47 elements). For bytes, it's like for shorts, bu