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)2) 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
An+1= 3*An
+ 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
- Partition the data using right most item as pivot and get the position of pivot
- QuickSort left to pivot position items.
- 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.
