(Quicksort) The recursive sorting technique called quicksort uses the following basic algo- rithm for a one-dimensional vector of values:

Question

a) Partitioning Step: Take the first element of the unsorted vector and determine its final location in the sorted vector (i.e., all values to the left of the element in the vector are less than the element’s value, and all values to the right of the element in the vector are greater than the element’s value—we show how to do this below). We now have one value in its proper location and two unsorted subvectors.
b) Recursion Step: Perform the Partitioning Step on each unsorted subvector. Each time the Partitioning Step is performed on a subvector, another value is placed in its final location of the sorted vector, and two unsorted subvectors are created. When a subvector consists of one element, that element’s value is in its final location (because a one-element vector is already sorted).
The basic algorithm seems simple enough, but how do we determine the final position of the first element value of each subvector? As an example, consider the following set of values (the value in bold is for the partitioning element—it will be placed in its final location in the sorted vector):
37 2 6 4 89 8 10 12 68 45
Starting from the rightmost element of the vector, compare each element value with 37
until an element value less than 37 is found; then swap 37 and that element’s value.
The first element value less than 37 is 12, so 37 and 12 are swapped. The new vector is
12 2 6 4 89 8 10 37 68 45
Element value 12 is in italics to indicate that it was just swapped with 37.
Starting from the left of the vector, but beginning with the element value after 12,
compare each element value with 37 until an element value greater than 37 is found—then swap 37 and that element value. The first element value greater than 37 is 89, so 37 and 89 are swapped. The new vector is
12 2 6 4 37 8 10 89 68 45
Starting from the right, but beginning with the element value before 89, compare each element value with 37 until an element value less than 37 is found—then swap 37 and that element value. The first element value less than 37 is 10, so 37 and 10 are swapped. The new vector is
12 2 6 4 10 8 37 89 68 45
Starting from the left, but beginning with the element value after 10, compare each element value with 37 until an element value greater than 37 is found—then swap 37 and that element value. There are no more element values greater than 37, so when we compare 37 with itself, we know that 37 has been placed in its final location of the sorted vector. Every value to the left of 37 is smaller than it, and every value to the right of 37 is larger than it.
Once the partition has been applied on the previous vector, there are two unsorted subvectors. The subvector with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subvector with values greater than 37 contains 89, 68 and 45. The sort continues recursively, with both subvectors being partitioned in the same manner as the original vector.
Based on the preceding discussion, write recursive function quickSortHelper to
sort a one-dimensional integer vector. The function should receive as arguments a starting index and an ending index on the original vector being sorted.

Answer 1

```
// Quick sort of a vector.
#include
#include
#include
#include
#include
using namespace std;

// function prototypes
void quickSortHelper( vector < int > &, int, int );
int partition( vector < int > &, int, int );
void swap( int * const, int * const );

int main()
{
const int MAX_NUMBER = 100;
const int SIZE = 10;
vector < int > vectorToBeSorted( SIZE );
int loop;

srand( time( 0 ) );

// randomly generate content
for ( loop = 0; loop < SIZE; loop++ )
vectorToBeSorted[ loop ] = rand() % MAX_NUMBER;

cout << "Initial vector values are:\n";

// print out values of the vector
for ( loop = 0; loop < SIZE; loop++ )
cout << setw( 4 ) << vectorToBeSorted[ loop ];

cout << "\n\n";

// if there is only one element
if ( SIZE == 1 )
cout << "Vector is sorted: " << vectorToBeSorted[ 0 ] << '\n';
else
{
quickSortHelper( vectorToBeSorted, 0, SIZE - 1 );
cout << "The sorted vector values are:\n";

for ( loop = 0; loop < SIZE; loop++ )
cout << setw( 4 ) << vectorToBeSorted[ loop ];

cout << endl;
} // end else

return 0;
} // end main

// recursive function to sort vector
void quickSortHelper( vector < int > &data, int first, int last )
{
int currentLocation;

if ( first >= last )
return;

currentLocation = partition( data, first, last ); // place an element
quickSortHelper( data, first, currentLocation - 1 ); // sort left side
quickSortHelper( data, currentLocation + 1, last ); // sort right side
} // end function quickSortHelper

// partition the vector into multiple sections
int partition( vector < int > &data, int left, int right )
{
int position = left;

// loop through the portion of the vector
while ( true )
{
while ( data[ position ] <= data[ right ] && position != right )
--right;

if ( position == right )
return position;

if ( data[ position ] > data[ right ])
{
swap( &data[ position ], &data[ right ] );
position = right;
} // end if

while ( data[ left ] <= data[ position ] && left != position )
++left;

if ( position == left )
return position;

if ( data[ left ] > data[ position ] )
{
swap( &data[ position ], &data[ left ] );
position = left;
} // end if
} // end while
} // end function partition

// swap locations
void swap( int * const ptr1, int * const ptr2 )
{
int temp;

temp = *ptr1;
*ptr1 = *ptr2;
*ptr2 = temp;
} // end function swap
```
Initial vector values are:
14 8 97 4 89 52 66 38 4 23
The sorted vector values are:
4 4 8 14 23 38 52 66 89 97