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:

- Divide the unsorted list into
*n*sub lists, each containing 1 element (a list of 1 element is considered sorted). - 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

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; } }