Sorting Algorithms Part 2

From a previous post we talked about few sorting algorithms. From this post I’m going to talk about few another sorting algorithms as well.

HEAP SORT

In the heap sort algorithm it divides its input into a sorted and an unsorted region, and it recursively reduce the unsorted region by extracting the largest element and moving that to the sorted region.The heap sort algorithm can be divided into two parts as below,

In the first step, a heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree.

In the second step, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array.

Let’s see how it works with an example,

List = 6, 5, 3, 1, 8, 7, 2, 4

1st step :

After creating the binary tree,

List = 8, 6, 7, 4, 5, 3, 2, 1

2nd step :

1st pass,

1, 6, 7, 4, 5, 3, 2, 8

2nd pass,

7, 6, 1, 4, 5, 3, 2, 8

3rd pass,

7, 6, 3, 4, 5, 1, 2, 8

4th pass,

2, 6, 3, 4, 5, 1, 7, 8

5th pass,

6, 2, 3, 4, 5, 1, 7, 8

6th pass,

6, 5, 3, 4, 2, 1, 7, 8

7th pass,

1, 5, 3, 4, 2, 6, 7, 8

8th pass,

5, 1, 3, 4, 2, 6, 7, 8

9th pass,

5, 4, 3, 1, 2, 6, 7, 8

10th pass,

2, 4, 3, 1, 5, 6, 7, 8

11th pass,

4, 2, 3, 1, 5, 6, 7, 8

12th pass,

1, 2, 3, 4, 5, 6, 7, 8

13th pass,

3, 2, 1, 4, 5, 6, 7, 8

14th pass,

1, 2, 3, 4, 5, 6, 7, 8

15th pass,

2, 1, 3, 4, 5, 6, 7, 8

16th pass,

1, 2, 3, 4, 5, 6, 7, 8

17th pass,

1, 2, 3, 4, 5, 6, 7, 8

Now let’s see the java code implementation for the above algorithm,

package Sorting;

import java.util.Arrays;

public class HeapSort {

    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;
    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};

    public static void main(String[] args) {
        sort(list);
        System.out.println(Arrays.toString(list));
    }

    public static void sort(int[] a0){
        a=a0;
        buildheap(a);
        for(int i=n;i>0;i--){
            swapped(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }

    public static void buildheap(int[] a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }

    public static void maxheap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            swapped(i,largest);
            maxheap(a, largest);
        }
    }

    public static void swapped(int i, int j){
        int swap=a[i];
        a[i]=a[j];
        a[j]=swap;
    }
}

MERGE SORT

Merge Sort is another sorting algorithm which is more efficient, general-purpose, comparison-based. Merge sort is a divide and conquer algorithm that was invented by John von Neumann. Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sub lists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sub lists to produce new sorted sub lists until there is only 1 sub list remaining. This will be the sorted list.

For an Example,

list = [9,8,4,6,7,5,1,2]

Step 01 :

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

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

[9][8][4][6][7][5][1][2]

Step 02 :

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

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

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

Let’s see the java code for the merge sort algorithm,

package Sorting;

import java.util.Arrays;

public class MergeSort {
    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};
    private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){
        MergeSort mms = new MergeSort();
        mms.sort(list);
        System.out.println(Arrays.toString(list));
    }

    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }

    private void doMergeSort(int lowerIndex, int higherIndex) {
        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            doMergeSort(lowerIndex, middle);
            doMergeSort(middle + 1, higherIndex);
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
    }
}

COUNTING SORT

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values. Then doing some arithmetic to calculate the position of each object in the output sequence.
Let’s see the java code implementation for the counting sort algorithm,
package Sorting;

import java.util.Arrays;

public class CountingSort {

    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};

    public static void main(String[] args) {
        System.out.println("Before: " + Arrays.toString(list));
        int [] sorted = sort(list);
        System.out.println("After:  " + Arrays.toString(sorted));
    }

    public static int[] sort(int[] array) {
        int[] aux = new int[array.length];
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            } else if (array[i] > max) {
                max = array[i];
            }
        }
        int[] counts = new int[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }
        counts[0]--;
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i - 1];
        }
        for (int i = array.length - 1; i >= 0; i--) {
            aux[counts[array[i] - min]--] = array[i];
        }
        return aux;
    }
}
So far from two blog posts I talked about sorting algorithms. There are so many other algorithms as well. So it’s up to you to choose the best one for the particular scenario and use. Here is a quick review about sorting algorithms,
Screenshot from 2016-08-25 16:37:05.png
I hope you got a clear idea about sorting algorithms. So see you with another important topic. Thank You!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s