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

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

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