The sorting algorithm I chose implements Quicksort. The full program developed using the Jeliot Tool is
below.
import jeliot.io.*;
public class QSort {
private static int
exchanges = 0;
private static int
array[] = {12,9,4,99,120,1,3,10,23,45,75,69,31,88,101,14,29,91,2,0,77};
/**
* @param args
*/
public static void
main(String[] args) {
System.out.println("The list before sorting is:");
printlist(array,array.length);
qsort(array,0,array.length-1);
System.out.println("\nThe list after sorting is:");
printlist(array,array.length);
System.out.println("\nThe number of exchanges is: " +
exchanges);
}
public static void
swap(int x,int y){
int temp;
temp =
array[x];
array[x] =
array[y];
array[y] =
temp;
exchanges++;
}
public static int
getkeyposition(int i,int j ){
return((i+j)
/2);
}
public static void
qsort(int list[],int m,int n){
int key,i,j,k;
if( m < n){
k =
getkeyposition(m,n);
swap(m, k);
key =
list[m];
i = m+1;
j = n;
while(i
<= j){
while((i
<= n) && (list[i] <= key))
i++;
while((j
>= m) && (list[j] > key))
j--;
if( i
< j)
swap(i,j);
}
swap(m,j);
qsort(list,m,j-1);
qsort(list,j+1,n);
}
}
public static void
printlist(int list[],int n){
for(int
i=0;i<n;i++)
System.out.print(list[i]+ "
");
}
}
Description:
Quicksort uses the simple strategy to
take the element at the center of list as the pivot using the function.
int getkeyposition(int i, j){
return(( i+j )/ 2);
}
In above algorithm, after the pivot is selected, the first
element is swapped with the pivot so that it will be in the first position. After
that, the pivot’s proper place in the list is obtained using function above. We
track the two partitions using the values i and j, and traverse the elements
until i becomes greater than j. When i becomes greater than j, we simply swap
the elements at those positions. Finally we swap jth element with
first element. This process is repeated recursively on the both sides of the
pivot until the array gets sorted.
Quicksort is more efficient than Insertion Sort because we
do not need to compare the adjacent elements in every pass. The use of pivots
(or the divide and conquer strategy) reduces the number of comparisons between
adjacent elements. This also removes the need to swap the elements a lot of
times, and hence sorts data faster.
This can be further
justified by the fact that the number of exchanges in Quicksort was only 36 compared to 114 in Insertion Sort. And
this value came as expected because Quicksort dramatically reduces the number
of exchanges or swap operations to be done.
Asymptotic Analysis:
In an average case, the array gets split into two
approximately equally sized sub-arrrays. If the size of a given array is n, it
gets split into two sub-arrays of size approximately n/2. Each of these
sub-arrays gets further split into two sub-arrays of size n/4, and this is
continued until the size equals 1.
That is to say, at first, it requires ‘n’ iterations to go
through n elements to select an appropriate pivot, and then it recursively
sorts left and right sub-arrays (which is similar to working with binary trees).
Hence, at average there are n*log n iterations. So, the average case complexity
is O(n log n).
If we think of worst case, the first or the last element is
always picked as the pivot, making one of the partitions empty. Hence, the
advantage of binary tree-like form is lost. The algorithm performs similar to
any simple sorting algorithm like Insertion Sort in such a case. Hence, the
worst case complexity is O(n2).
