Question

Write program in C

Question 1 •

try to implement median3() function and trace what happened to array.

median3 (int array[], int left, int right){

// to do …

}

Question 2.

•Try to implement quicksort() partition phase.

quicksort(int array[], int left, int right){

// to do…
}

Question 3.

Try to finish the whole process of quicksort

Answer 1

1.

import java.util.Random;
public class QsortTest
{
    public static void main (String [] args)
    {
        Comparable [] a;
        Random   ran;
        ConsoleReader console = new ConsoleReader(System.in);

        System.out.println("How many randomly generated integers to sort?");
        int n = console.readInt();

        ran  = new Random();
        a    = new Comparable[n]; // get array of this number of objects
        for (int i=0;i<n;i++)
        {
           a[i] = new Integer(ran.nextInt(100));
        }

        System.out.println("\nOriginal Array:");
        printArray(a);  
        
        quicksort(a);

        System.out.println("\n\nSorted Array:");
        printArray(a);
    } // end main

// --------------------------------------------------------------

    public static void printArray(Comparable [] a)
    {
        for (int i=0;i<a.length;i++){
            int j = ((Integer) a[i]).intValue();
            System.out.print(j + " ");
        }
        System.out.println();
    }

// --------------------------------------------------------------
// driver to recursive sort array of Comaprables using quicksort
// with median of 3 partition. Use insertion sort for small arrays

    public static void quicksort(Comparable [] a)
    {
        quicksort(a,0,a.length-1);
    }

    private static void quicksort(Comparable [] a, int left, int right)
    {
        final int CUTOFF = 3;
        if (right-left+1 < CUTOFF) { // need at least 3 elements for qs
            insertionSort(a,left,right);
        }
        else {
            Comparable pivot = median3(a,left,right); // get pivot

            int i = left, j = right-1;                // do the partitioning
            while (i < j){
                while (a[++i].compareTo(pivot) < 0) {}; // advance left ptr
                while (a[--j].compareTo(pivot) > 0) {}; // decrement rt ptr
                swap(a,i,j);
            } // end while
            
            swap(a,i,j);        // undo last (incorrect) swap
            swap(a,i, right-1);   // restore pivot
            
            quicksort(a,left,i-1);   // recursive calls on smalelr
            quicksort(a,i+1,right);  // and larger subarrays
        } // end else

    } // end quicksort

// --------------------------------------------------------------

// median of 3 partitioning - put the 3 in order, and hide pivot
    private static Comparable median3(Comparable [] a, int left, int right)
    {
        int center = (left+right)/2;
        if (a[center].compareTo(a[left]) < 0)
            swap(a,left,center);

        if (a[right].compareTo(a[left]) < 0)
            swap(a,left,right);

        if (a[right].compareTo(a[center]) < 0)
            swap(a,center,right);

        // put pivot at NEXT to rightmost position
        swap(a,center,right-1);
        return a[right-1];    // return the pivot too
            
    }

// --------------------------------------------------------------

// swap the elements at index i and j
    private static void swap(Comparable a[], int i, int j)
    {
        Comparable tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static void insertionSort(Comparable a[], int left, int right)
    {
        int j;

        for (int p=left+1; p<= right; p++){
            Comparable tmp = a[p];
            for (j=p; j>left && tmp.compareTo( a[j-1]) < 0; j--)
                a[j] = a[j-1];
            a[j] = tmp;
        }

    } // end insertionSort

} // end class QsortTest

2.int partition(int[] A, int lower, int pivot_index, int upper)
//@requires 0 <= lower && lower <= pivot_index;
//@requires pivot_index < upper && upper <= \length(A);
//@ensures lower <= \result && \result < upper;
//@ensures ge_seg(A[\result], A, lower, \result);
//@ensures le_seg(A[\result], A, \result, upper);
{
// Hold the pivot element off to the left at "lower"
int pivot = A[pivot_index];
swap(A, lower, pivot_index);
int left = lower+1;
int right = upper;
while (left < right)
//@loop_invariant lower+1 <= left && left <= right && right <= upper;
//@loop_invariant ge_seg(pivot, A, lower+1, left); // Not lower!
//@loop_invariant le_seg(pivot, A, right, upper);
{
if (A[left] <= pivot) {
left++;
} else {
//@assert A[left] > pivot;
swap(A, left, right-1);
right--;
}
}
//@assert left == right;
swap(A, lower, left-1);
return left-1;
}

3.

void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
  
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
  
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
  
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
  
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
  
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}
  
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}
Output:

Sorted array:
1 5 7 8 9 10