Implementing a sorting algorithm in Jeliot tool

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 j^th 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(n²).