Challenge: Look up Hoare\'s quicksort algorithm. Write loop invariant assertions

Question

Challenge: Look up Hoare's quicksort algorithm. Write loop invariant assertions that make the logic of quicksort easy to understand. You may also want preconditions and postconditions. A precondition is a formula that the programmer assumes will be true when an algorithm is invoked (called): the programmer announces that if the precondition is not true, then the algorithm probably will not do what it is supposed to do. A postcondition is a formula expressing something that is supposed to be true after the algorithm finishes-assuming the preconditions are satisfied, of course.

Explanation / Answer

//QuickSort using Hoare's partition scheme.
#include<bits/stdc++.h>
using namespace std;

//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 doPartition(int myArr[], int l, int h)
{
//Parameter l for starting index
//Parameter h for ending index
//Initializes the pivot to the low index position of the array
int pivot = myArr[l];
int i = l - 1, j = h + 1;

while (true)
{
// Find leftmost element greater than or equal to pivot
//Loops till array's i index position is less than pivot value
do
{
//Increase the i value by one
i++;
} while (myArr[i] < pivot);

// Find rightmost element smaller than or equal to pivot
//Loops till array's j index position is greater than the pivot value
do
{
//Decrease the j value by one
j--;
} while (myArr[j] > pivot);

// If two pointers met.
if (i >= j)
//Returns j value
return j;
//Calls mySwap for swapping
swap(myArr[i], myArr[j]);
}//End of while loop
}//End of function

//Recursion function for quick sort
void quickSort(int myArr[], int l, int h)
{
//parameter l for starting index,
//parameter h ending index

if (l < h)
{
//pi is partitioning index, myArr[p] is now at right place
int pi = doPartition(myArr, l, h);

// Separately sort elements before partition and after partition
quickSort(myArr, l, pi);
quickSort(myArr, pi + 1, h);
}//End of if
}//End of function

//Function to print an array
void printArray(int myArr[], int len)
{
//Loops till length of the array
for (int counter = 0; counter < len; counter++)
printf("%d ", myArr[counter]);
printf(" ");
}

// Main function definition
int main()
{
//To store how many numbers user wants to sort
int len;
//Accept the length of array
cout<<" Enter how many elements you want? ";
cin>>len;
//Creates an array based on the length entered by the user
int *myArray = (int *)malloc(len * sizeof(int));
//Loops till length
for(int counter = 0; counter < len; counter++)
//Accepts data from the user and stores it in array
cin>>myArray[counter];
//Calls the method to sort
quickSort(myArray, 0, len-1);
printf("Sorted array: ");
//Display the sorted array
printArray(myArray, len);
return 0;
}//End of main

Sample Output 1:

Enter how many elements you want? 5
45
12
5
78
6
Haore's Quick Sort array:
5 6 12 45 78

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.