Java Programming Implement an optimized version of quicksort

Java Programming

Implement an optimized version of quicksort and experiment with combinations of the following:

Use the following int array when doing this problem. Make sure the order is the same as specified below.

1,53,86,21,49,32,90,65,33,11,34,68,54,32,78,80,35,22,96,59,265,44324,123,3123,25435

Pivot: first element, middle element, random element, median of three, median of five.

/* Quicksort example */

private static <AnyType extends Comparable<? super AnyType>>

void quicksort(AnyType [] a, int left, int right)

{

           if ( left + CUTOFF <= right)

{

            AnyType pivot = median3(a, left, right);

            int i = left, j = right -1;

            for(;;)

           {

                while( a[ ++i ].compareTo( pivot ) < 0 ) { }

                while( a[ --j ].compareTo( pivot ) > 0 ) { }

                if (i < j)

                    swapRefernces( a, i, j );

                else

                   break;

            }

        swapReferences( a, i, right - 1);

        quicksort( a, left, i - 1);

        quicksort( a, i +1, right);

}

          else

             insertionSort( a, left, right);

}

For Median Of Five, take the first, last, middle and the element at around 1/4 of the way through the array and the element around 3/4 of the way through the array. Modfiy the code as necessary

a.) write new methods that use the different pivot schemes. Call them using the sample array and verify they work.

b.) Alter the code to use 0, 5, 10, 15 and 20 as the cutoff values. You will need to have different methods.

c.) Which way do you feel is the most efficient? Why? (You don\'t need a math proof here, just a text explanation)

Solution

program

static void OptimiQSort(ref int[] Arr, int Left, int Right)
{
int Pivot;
Pivot = QSort(ref Arr, Left, Right);
if(Left < Pivot - 1)
{
OptimiQSort(ref Arr, Left, Pivot - 1);
}
if(Right > Pivot + 1)
{
OptimiQSort(ref Arr, Pivot + 1, Right);
}
}

static int QSort(ref int[] Arr, int Left, int Right)
{
int Pivot;
Pivot = Arr[Left];
while(Left < Right)
{
while((Arr[Right] >= Pivot) && (Left < Right))
{
Right--;
}
if(Left != Right)
{
Arr[Left] = Arr[Right];
Left++;
}
while((Arr[Left] <= Pivot) && (Left < Right))
{
Left++;
}
if(Left != Right)
{
Arr[Right] = Arr[Left];
Right--;
}
}   
Arr[Left] = Pivot;
return Left;
}