Quick Sort With Minor Improvements

Improvements:

1. Setting the element with index hi (the pivot element) equal to the median of the three elements lo, hi and (lo+hi) / 2 so that the probability that it lies in between the values is more.

2. Using the faster Insertion sort if the number of elements in the sub array is less than some predefined value (the value 5 is used here).

Source:

package QuickSort;

import java.util.Arrays;

public class QuickSort {

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

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) {
            return;
        }

        //If array size is less than 5, we will use Insertion Sort
        if (hi - lo <= 5) { 
            InsertionSort.insertionSort(array, lo, hi);
            return;
        }

        int m = median(array, lo, (lo + hi) / 2, hi); 
        swap(array, m, hi);

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i < hi; ++i) {
            if (array[i] < array[hi]) {
                swap(array, partitionIndex, i);
                partitionIndex++;
            }
        }
        swap(array, partitionIndex, hi);
        return partitionIndex;
    }

    public static int median(int[] x, int a, int b, int c) {
        if (x[a] > x[b] && x[a] > x[c]) { if (x[b] > x[c]) return b; else return c; }
        else if (x[b] > x[a] && x[b] > x[c]) { if (x[a] > x[c]) return a; else return c; } 
        else if (x[c] > x[a] && x[c] > x[b]) { if (x[a] > x[b]) return a; }
        return b;
    }

    public static void swap(int array[], int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

class InsertionSort {

    public static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; ++i) {
            int j = i;
            while (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                if (--j == 0) {
                    break;
                }
            }
        }
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

Bottom Up Merge Sort Java Implementation

Bottom up merge sort sorts the array without using recursion. It is 10% slower than the top down (recursive) mergesort. The idea is to start sorting the array elements from the start in groups of 2, 4, 8, 16, and so on (powers of two). So that the effect is the same as the recursive algorithm.
Here is a trace for sorting numbers 13,12, ..., 1

 

Source:

import java.util.Arrays;

public class BottomUpMergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; 
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
        System.out.println(Arrays.toString(orig));
        System.out.println("start = "+start+" mid = "+mid+" end = "+end);
        System.out.println(Arrays.toString(aux)+"\n");
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        int N = orig.length;
        for (int sz = 1; sz < N; sz *= 2) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(orig, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N-1));
            }
        }
    }

    public static void main(String[] args) {
        int array[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }
}

lo < N - sz 
takes care to see that the mid value falls before end. 

lo < N - sz
lo + sz < N
lo + sz - 1 < N - 1
mid < N - 1

Math.min() takes care to see that end does not extend beyond the last index.

Output:

[11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 0 mid = 0 end = 1
[10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 2 mid = 2 end = 3
[10, 11, 8, 9, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 7, 6, 5, 4, 3, 2, 1]
start = 4 mid = 4 end = 5
[10, 11, 8, 9, 6, 7, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1]
start = 6 mid = 6 end = 7
[10, 11, 8, 9, 6, 7, 4, 5, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 3, 2, 1]
start = 8 mid = 8 end = 9
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
start = 0 mid = 1 end = 3
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 0]
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 1]
start = 4 mid = 5 end = 7
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 0]
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 1]
start = 8 mid = 9 end = 10
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
start = 0 mid = 3 end = 7
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
start = 0 mid = 7 end = 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Merge Sort Implementation with minor Improvements [Java]

Here is the basic merge sort algorithm implementation to which we will be adding some improvements:

Source: 

import java.util.Arrays;
 
public class MergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start;  
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while (j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while (i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }   
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(orig, aux, start, mid); 
        sort(orig, aux, mid + 1, end); 
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length]; 
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

Improvements that we can add:

1. Skip merge procedure if the elements in the two sorted halves to merge are already in ascending order (i.e. if firstHalf's end element <= secondHalf's first element so no merge is needed at all).
2. We can avoid copying back from auxiliary array every time merge is called by interchanging the roles of original array and auxiliary array during recursion. (The final result will be stored in the auxiliary array.)

Source: 

import java.util.Arrays;

public class MergeSort2 {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; //Point #1
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(aux, orig, start, mid);        //Point #2
        sort(aux, orig, mid + 1, end);      
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        System.arraycopy(array, 0, aux, 0, array.length);  //Be careful, both arrays must be the same initially!
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(aux));
    }
}

Quick Sort Implementation [Java]

Quicksort makes O(n log n) comparisions to sort n items. In the worst case, it makes O(n^2) comparisions. Quicksort is often faster in practice than other O(n log n) algorithms. Qucicksort is a comparison sort.

Quicksort is NOT a stable sort.
Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

https://www.youtube.com/watch?v=COk73cpQbFQ

Code:

import java.util.Arrays;

public class QuickSort {

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

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) return;

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i <= hi; ++i) {
            if (array[i] < array[hi]) {
                int temp = array[partitionIndex];
                array[partitionIndex] = array[i];
                array[i] = temp;
                partitionIndex++;
            }
        }
        int temp = array[partitionIndex];
        array[partitionIndex] = array[hi];
        array[hi] = temp;
        return partitionIndex;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

Selection Sort Implementation [Java]

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

Code:

import java.util.Arrays;

public class SelectionSort {

    public static int getMinIndex(int[] array, int from){
        int min = Integer.MAX_VALUE, minIndex = -1;
        for(int i=from;i<array.length;++i){
            if(array[i]<min){
                min = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
    public static void selectionSort(int[] array){
        for(int i=0;i<array.length;++i){
            int minIndex = getMinIndex(array, i);
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;            
        }
    }
    public static void main(String[] args){
        int arr[] = {5, 4, 3, 2, 1};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Output:

[1, 2, 3, 4, 5]

as expected!

Heap Sort Implementation Java [Heap Sort][Java]

Heapsort is a comparison-based sorting algorithm. Heapsort is part of the selection sort family; it improves on the basic selection sort by using a logarithmic-time priority queue rather than a linear-time search. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

Worst case performance = O(n log n)

This video is really helpful if you want to have a good understanding of heaps and sorting using min/max heaps. 

[MIT OpenCourseWare]
http://www.youtube.com/watch?v=B7hVxCmfPtM

Code:

class Heap {

    private static int[] array;
    private static int heap_size;

    private static int leftChild(int node) {
        return (node * 2 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 + 1 : -1;
    }

    private static void constructHeap() {
        for (int i = heap_size / 2; i > 0; --i) {
            max_heapify(i);
        }
    }

    private static void max_heapify(int node) {
        int consider;
        if (leftChild(node) == rightChild(node)) {  //Missing nodes (both return -1)
            return;
        } else if (leftChild(node) == -1) {         //left node missing, consider the right one
            consider = rightChild(node);
        } else if (rightChild(node) == -1) {        //right node missing, consider the left one
            consider = leftChild(node);
        } else {                                    //both nodes present, evalute which one to consider
            consider = array[leftChild(node)] >= array[rightChild(node)] ? leftChild(node) : rightChild(node);
        }

        if (array[node] < array[consider]) {
            int temp = array[node];
            array[node] = array[consider];
            array[consider] = temp;
            max_heapify(consider);
        }
    }

    private static int extractMax() {
        if (heap_size == 0) {
            System.err.println("Error: Heap is empty!");
            return -1;
        }
        int maxValue = array[1];
        int temp = array[1];
        array[1] = array[heap_size];
        array[heap_size] = temp;
        heap_size--;
        return maxValue;
    }

    public static void heapSort(int[] array_input) {

        //array to sort
        array = array_input;
        /*
         max_heap size = array.length-1 (-1 for the 0th index that we are NOT going to consider)
         The user should not have to care about leaving the 0th index empty.
         But we can't use index 0 due to the rightChild() and leftChild() calculations for
         indexes. We need to make a copy of this array so that the new copy has size (array_input+1). 
         */
        heap_size = array.length - 1;
        constructHeap();

        for (int i = array.length - 1; i > 0; --i) {
            array[i] = extractMax();
            max_heapify(1);
        }
    }

    public static void main(String[] args) {
        int[] array = {0, 7, 5, 99, 3, 2, 1, 22, 33, 42, 1, 332, 1};
        heapSort(array);
        for (int i = 1; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}

Output:

1 1 1 2 3 5 7 22 33 42 99 332

as expected!

This code is good to understand the working. But if you want the user to just input an array (not caring about index 0) you need to accomodate for the included 0th index.

Important points where code needs to be changed in this case:

During the calculation of leftChild and rightChild -

    private static int leftChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 2 <= heap_size) ? node * 2 + 1 : -1;
    }

Modified code (full):

class Heap {

    private static int[] array;
    private static int heap_size;

    private static int leftChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 2 <= heap_size) ? node * 2 + 1 : -1;
    }

    private static void constructHeap() {
        for (int i = heap_size / 2; i >= 0; --i) {
            max_heapify(i);
        }
    }

    private static void max_heapify(int node) {
        int consider;
        if (leftChild(node) == rightChild(node)) {  //Missing nodes (both return -1)
            return;
        } else if (leftChild(node) == -1) {         //left node missing, consider the right one
            consider = rightChild(node);
        } else if (rightChild(node) == -1) {        //right node missing, consider the left one
            consider = leftChild(node);
        } else {                                    //both nodes present, evalute which one to consider
            consider = array[leftChild(node)] >= array[rightChild(node)] ? leftChild(node) : rightChild(node);
        }

        if (array[node] < array[consider]) {
            int temp = array[node];
            array[node] = array[consider];
            array[consider] = temp;
            max_heapify(consider);
        }
    }

    private static int extractMax() {
        if (heap_size == -1) {
            System.err.println("Error: Heap is empty!");
            return -1;
        }
        int maxValue = array[0];
        int temp = array[0];
        array[0] = array[heap_size-1];
        array[heap_size-1] = temp;
        heap_size--;
        return maxValue;
    }

    public static void heapSort(int[] array_input) {

        array = array_input; 
        heap_size = array.length;
        constructHeap();

        for (int i = array.length-1; i >= 0; --i) {
            array[i] = extractMax();
            max_heapify(0);
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 5, 4, 3, 5, 2, 1};
        heapSort(array);
        for (int i = 0; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}

Output:

1 2 3 4 5 5 5

as expected!

Shell Sort Implementation [Java]

This program implements the Shell Sort Algorithm.

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting elements far apart from each other and progressively reducing the gap between them. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.

Code:

import java.util.Arrays;

public class ShellSortILimit { 
    
    public static void shellSort(int[] a) {
        int factor = a.length / 2;
        while (factor != 0) {
            insertionSort(a, factor);
            System.out.println("Factor " + factor + " processed: " + Arrays.toString(a));
            factor /= 2;
        }
    }

    private static void insertionSort(int[] a, int factor) {
        for(int i=0, j=factor;j<a.length;++i, ++j){
            int tempI = i, tempJ = j;
            System.out.println(i+" "+j);
            while(a[tempJ]<a[tempI]){
                /*
                Integer class is immutable. So you can't
                make a function like 
                void swap(Integer a, Integer b){} 
                to swap values. You have to do it manually.
                */
                int temp = a[tempI]; 
                a[tempI] = a[tempJ];
                a[tempJ] = temp;
                tempI--; tempJ--; 
                if(tempI == -1) break;
            } 
        }
    }

    public static void main(String[] args) {
        int test[] = new int[]{0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        shellSort(test);
        System.out.println(Arrays.toString(test)); 
    }
}

Output:

0 5
1 6
2 7
3 8
4 9
5 10
Factor 5 processed: [0, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5]
0 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
Factor 2 processed: [0, 2, 1, 0, 3, 4, 7, 6, 5, 8, 9]
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
Factor 1 processed: [0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Insertion Sort - Implementation [Java]

The insertion sort is really very easy. I thought of practicing it before implementing the Shell Sort.

Code:

import java.util.Arrays;

public class InsertionSort {
    public static void  insertionSort(int[] a){
        for(int i=1;i<a.length;++i){
            int j = i;
            while(a[j]<a[j-1]){
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp; 
                if(--j==0)break;
            }
        }
    }
    public static void main(String[] args){
        int test[] = {4, 3, 1, 2, 1};
        insertionSort(test);
        System.out.println(Arrays.toString(test));
    }
}

Output:

[1, 1, 2, 3, 4]

Merge Sort Implementation In Java

This program implements Merge Sort Algorithm.

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm. Have a quick read here if you like. 

Code:

import java.util.Arrays;

public class MergeSort { 
    
    public static void mergeSort(int[] orig){
        int temp[] = new int[orig.length];
        mergeSorter(0, orig.length-1, orig, temp);
    }
    
    private static void mergeSorter(int beg, int end, int[] orig, int[] temp) {
        if (beg == end) {
            return;
        }  
        mergeSorter(beg, (beg + end) / 2, orig, temp); 
        mergeSorter((beg + end) / 2 + 1, end, orig, temp);  
        merge(beg, end, orig, temp); 
        System.arraycopy(temp, beg, orig, beg, (end-beg+1));
    } 
    
    private static void merge(int beg, int end, int[] orig, int[] temp){
        int s1 = beg;           //first half starting position
        int e1 = (beg+end)/2;   //first half ends here
        int s2 = (beg+end)/2+1; //second half starts here
        int e2 = end;           
        
        int i = beg, l = s1, r = s2;
        while(l<=e1 && r<=e2){ 
            if (orig[l] >= orig[r]) {
                temp[i] = orig[r];  
                r++;
            } else if (orig[l] < orig[r]) {
                temp[i] = orig[l];  
                l++;
            } 
            i++;
        } 

        if (l == e1+1) { 
            System.arraycopy(orig, r, temp, i, e2-r+1);  
        } else if (r == e2+1) { 
            System.arraycopy(orig, l, temp, i, e1-l+1); 
        }   
    }
    
    public static void main(String[] args) { 
        int[] input = new int[]{5, 6, 3, 2, 2, 9, 9, 0};    //test array
        MergeSort.mergeSort(input);
        System.out.print(Arrays.toString(input));
    }
}

Output:
[0, 2, 2, 3, 5, 6, 9, 9] 

as expected.