Data Structure: Advance Sorting Algorithm

In this post I am writing about two advance sorting algorithm: Shell Sort and Quick Sort. These sorts both operate faster than simple sorts. Shell sort take about O(N(logN)²) time and Quick sort takes O(N*logN) time.

Shell Sort

The Shell sort is good for medium sized array, perhaps up to few thousand items. Shell sort implementation is short and simpler than Quick sort. Shell sort is typically based on Insertion sort. To review Insertion sort, read my previous post. At any point in insertion sort, data item at the left of marker is internally sorted. Suppose there is an item, smallest of all at the right end of the array. To insert this item at proper position, all the N items must be shifted to make space at the front of the array. This is a drawback of Insertion sort. Shell sort addresses this problem. In Shell sort, widely spaced items are insertion sorted. This brings the items many spaces closer to their proper position. The spacing between the elements for insertion sort is called increment and traditionally represented as letter h.

Let’s sort an array of 10 items with increment 4. So, items at 0, 4 and 8 will be insertion sorted first, then 1, 5 and 9. This process will continue until all items have been 4-sorted, this means that all the items four cell apart are sorted among themselves. At the end of this first set of iteration, the array can be thought of four sorted sub arrays: (0, 4, 8), (1, 5, 9), (2, 6) and (3, 7). These sub arrays are interleaved but otherwise independent.

For an array of size 10, the initial gap is 4 but for larger array gap should start out much larger. This gap is then diminished repeatedly until it becomes 1. The sequence of intervals is called gap sequence or interval sequence. Donal Ervin Knuth recommended an interval sequence. The interval sequence can be generated by

A_n+1= 3*A_n + 1

Java Code for Shell Sort

public void shellSort()

{

int inner, outer;

long temp;

int h = 1;

while(h <= nElems/3)

h = h*3 + 1;

while(h>0)

{

for(outer=h; outer<nElems; outer++)

{

temp = theArray[outer];

inner = outer;

while(inner > h-1 && theArray[inner-h] >= temp)

{

theArray[inner] = theArray[inner-h];

inner -= h;

}

theArray[inner] = temp;

}

h = (h-1) / 3;

}

}

}

Quick Sort

Quick sort is most popular and fastest in majority of situation. Partitioning algorithm is required to understand Quick Sort. So I will discuss Partitioning algorithm first.

Partitioning data is dividing data items in two groups. All the items greater that key data are in one group and all the items less than key data are in another group. The key data item is called pivot. This pivot can be one among the data items to be divided or it can be any other data.

Java code for Partition

public int partition(int left, int right, long pivot)

{

int leftPtr = left - 1;

int rightPtr = right + 1;

while(true)

{

while(leftPtr < right && theArray[++leftPtr] < pivot);

while(rightPtr > left && theArray[--rightPtr] > pivot);

if(leftPtr >= rightPtr)

break;

else

swap(leftPtr, rightPtr);

}

return leftPtr; // return partition

}

Quick short uses partitioning algorithm to sort the data. Data is first partitioned using a pivot. Then left and right sub arrays are Quick sorted. Selection of pivot is very crucial in this sorting algorithm. We are taking the rightmost item in the array as pivot. So, after first round of quick sort pivot(right most element) is at proper position and left and right sub array will be quick sorted now.

Step to implement Quick Sort

1. Partition the data using right most item as pivot and get the position of pivot
2. QuickSort left to pivot position items.
3. QuickSort pivot to right position items.

It is using recursive function to implement quick sort.

Java code for Quick Sort

public void recQuickSort(int left, int right)

{

if(right-left <= 0)

return;

else

{

long pivot = theArray[right];

int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

}

Since we have chosen to take right most element as a pivot, we have to modify the Partition code given above in the post.