In a simple implementation of quicksort based below written in C code . Take a l
ID: 3644372 • Letter: I
Question
In a simple implementation of quicksort based below written in C code . Take a look at the partition method. Identify an appropriate invariant for the while loop, and prove that it is indeed an invariant. Then prove that the partition method is correct, that is, prove that the postcondition is always true when the method returns.The Simple C code
public class SimpleQuickSort
{
public static void quicksort(int[] arr)
{
quicksort(arr, 0, arr.length - 1);
}
private static void quicksort(int[] arr, int first, int last)
{
if (first >= last) return;
int pos = partition(arr, first, last);
quicksort(arr, first, pos - 1);
quicksort(arr, pos + 1, last);
}
// Postcondition: for all x < pos, arr[x] < pivot, and
// for all x >= pos, arr[x] >= pivot, and
// arr[pos] = pivot
private static int partition(int[] arr, int first, int last)
{
int pivot = arr[last];
int pos = first;
int q = first;
while (q < last)
{
if (arr[q] < pivot)
{
swap(arr, q, pos);
++pos;
}
++q;
}
swap(arr, pos, last);
return pos;
}
private static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Explanation / Answer
Functions cannot be called before they are declared.
You have called the functions quickSort and partition before they were declared.