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 Test 1 3 5 7 9 10 11 12 13 16 24 Test 2 And Bangalore I In Is M My Name Raghav Stay

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 =1) { // h-sort the array. // insertion sort for(int i = h; i = 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 key1, int key2) { return key1 Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

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 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 Unsorted array : 11 13 13 13 7 12 16 9 6 6 6 15 2 4 6 Sorted array : 2 4 6 6 6 6 7 9 11 1...

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 mid) { array[k++] = aux[j++]; } else if(j > high) { array[k++] = aux[i++]; } else if(less(aux[i], aux[j])) { array[k++] = aux[i++]; } else { array[k++] = aux[j++]; } } } 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 key1, int key2) { return key1 Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

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 mid) { aux[k++] = array[j++]; } else if(j > high) { aux[k++] = array[i++]; } else if(less(array[j], array[i])) { aux[k++] = array[j++]; } else { aux[k++] = array[i++]; } } } 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 key1, int key2) { return key1 Unsorted array : 11 13 7 12 16 9 24 15 2 4 6 0 20 22 5 10 3 Sorted array : 0 2 3 4 5 6 7 9 10 11 12 13 15 16 20 22 24

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 mid) { array[k++] = aux[j++]; } else if(j > high) { array[k++] = aux[i++]; } else if(less(aux[i], aux[j])) { array[k++] = aux[i++]; } else { array[k++] = aux[j++]; } } } 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 key1, int key2) { return key1 Unsorted array : 11 13 7 12 16 9 24 15 2 4 6 0 20 22 5 10 3 Sorted array : 0 2 3 4 5 6 7 9 10 11 12 13 15 16 20 22 24

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 mid) { array[k++] = aux[j++]; } else if(j > high) { array[k++] = aux[i++]; } else if(less(aux[i], aux[j])) { array[k++] = aux[i++]; } else { array[k++] = aux[j++]; } } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; ar...

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 mid) { array[k++] = aux[j++]; } else if(j > high) { array[k++] = aux[i++]; } else if(less(aux[i], aux[j])) { array[k++] = aux[i++]; } else { array[k++] = aux[j++]; } } } 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 key1, int key2) { return key1 Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

  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 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 + " "); } } public static void main (String[] args) { // Test average case int[] array = new int[] {11,13,7,12,7,7,7,7,7,16,9,24,5,5,5,5,5,7,7,7,10,3}; System.out.println("Unsorted array : "); display(array); sort(array); System.out.println("\nSorted array : "); display(a...

private static void sort(Comparable[] a, int lo, int hi) { if (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 = j) { break; } // swap array[i] with array[j] swap(array, i, j); } // swap array[low] with array[j] swap(array, low, j); // all elements before jth index are less then jth element // and all elements after jth elements are greater than jth element // so jth element is the partition elemrnt. Return index j return j; } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } private static boole...

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 0; i--) { int index = random.nextInt(i + 1); // Simple swap swap(array, i, index); } } 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])) { ...

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 = j) { break; } // swap array[i] with array[j] swap(array, i, j); } // swap array[low] with array[j] swap(array, low, j); // all elements before jth index are less then jth element // and all elements after jth elements are greater than jth element // so jth element is the partition elemrnt. Return index j return j; } 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 key1, int key2) { return key1 Output Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

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 Output Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

class InsertionSort { private static int[] array; private void sort() { for(int i = 1; i 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] Output Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

class BubbleSort { private static int[] array; private void sort() { boolean sorted = true; for(int i = 0; i Output Unsorted array : 11 13 7 12 16 9 24 5 10 3 Sorted array : 3 5 7 9 10 11 12 13 16 24

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 ele...

 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 t...