Question

quickSort function. Calling previous functions already implemented.

This is a bit different type of quicksort function where my partition function has 3 parameters instead of 4.

So I need to write a function quicksort that actually puts all 3 of my functions together and finalizes the sorting process

"There should be almost nothing done besides calling the other 3 functions and recursively calling itself (except to check for basecase)

class quicksort
{
private:
int left;
int right;
int* array;
  
public:
void swapListValues(int* array, int left, int right );
int findAndSwapPivot(int* array, int left, int right );
int partitionList(int* array, int left, int right, int pivot );
void quickSort(int* array, int left, int right );
};

----

void quicksort::swapListValues(int* array, int left, int right )
{
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}

----

int quicksort::findAndSwapPivot(int* array, int left, int right )
{
int temp = (right + left) / 2;
int pivot = array[temp];

swapListValues(array, temp, right );

return pivot;
  
}

----

int quicksort::partitionList(int* array, int left, int right, int pivot) {

// one lower than range
int smallerIndex = left-1;
// start at rightmost element
int largerIndex = right + 1;

//infinite loop while conditions are met
for (;;)
{
// find a larger-than-pivot element starting from the left
while (array[++smallerIndex] < pivot);

while (pivot < array[--largerIndex])
{
if (largerIndex == left)
break;
}

if (smallerIndex >= largerIndex) break;
swapListValues(array, smallerIndex, largerIndex);
}

// return the index of the pivot-position
return smallerIndex;
}

void quicksort::quickSort(int* array, int left, int right )
{

}

main function (just uncomment to test)

int main(int argc, char** argv)

{

const int MAX_TEST_SIZE = 100;
int testvals[MAX_TEST_SIZE];
int expected[MAX_TEST_SIZE];
int length;
  
quicksort sortAndSearch;

cout << "Test quickSort() -----------------------------------------------" << endl;

// sort a list of size 1
int length = 1;
memcpy(testvals, (const int[]){8},
sizeof(int) * length);
memcpy(expected, (const int[]){8},
sizeof(int) * length);
// sortAndSearch.quickSort(testvals, 0, length-1);
// cout << "quickSort() test 1, sort list of size 1" << endl
// << " expected: " << tostring(expected, length) << endl
// << " actual: " << tostring(testvals, length) << endl
// << endl;
// assert(listsAreEqual(testvals, expected, length));

return 0;

}

Answer 1

//~ quicksort working but i have problem using bottom commented code
//~ calling tostring(), assert() functions. may be this is because gcc version problem
//~ should be working on your pc... let me know if there is problem. thanks...

#include <iostream>
#include <iomanip>
#include <assert.h>
using namespace std;

class quicksort {
private:
int left;
       int right;
       int * array;

public:
       void swapListValues(int * array, int left, int right);
       int findAndSwapPivot(int * array, int left, int right);
       int partitionList(int * array, int left, int right, int pivot);
       void quickSort(int * array, int left, int right);
};

void quicksort::swapListValues(int * array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
  
int quicksort::findAndSwapPivot(int * array, int left, int right) {
int temp = (right + left) / 2;
int pivot = array[temp];
swapListValues(array, temp, right);
return pivot;

}
  
int quicksort::partitionList(int * array, int left, int right, int pivot) {
// one lower than range
int smallerIndex = left - 1;
// start at rightmost element
int largerIndex = right + 1;
//infinite loop while conditions are met
for (;;) {
// find a larger-than-pivot element starting from the left
while (array[++smallerIndex] < pivot);
while (pivot < array[--largerIndex]) {
if (largerIndex == left)
break;
}
if (smallerIndex >= largerIndex) break;
swapListValues(array, smallerIndex, largerIndex);
}
// return the index of the pivot-position
return smallerIndex;
}
void quicksort::quickSort(int * array, int left, int right)
   {
       if (left < right)
       {
           /* piv is index of the pivot-position */
           int piv = array[right]; //starting from right initialy
           piv = partitionList(array, left, right, piv);
  
           // Separately sort elements before
           // partition and after partition
           quickSort(array, left, piv - 1);
           quickSort(array, piv + 1, right);
       }   
   }

//main function(just uncomment to test)
int main(int argc, char ** argv) {
const int MAX_TEST_SIZE = 100;
int testvals[MAX_TEST_SIZE];
int expected[MAX_TEST_SIZE];
int length;

quicksort sortAndSearch;
cout << "Test quickSort() -----------------------------------------------" << endl;
// sort a list of size 1
length = 6;
memcpy(testvals, (const int[]) {
8,2,3, 1,4,5
},
sizeof(int) * length);
memcpy(expected, (const int[]) {
1,2,3, 4,5,8
},
sizeof(int) * length);
  
sortAndSearch.quickSort(testvals, 0, length-1);
  
//added for loop to print sorted array - testvals
for (int i = 0; i < length; i++)
       cout<< testvals[i] << " ";          
      
  
//~ cout << "quickSort() test 1, sort list of size 1" << endl
//~ << " expected: " << tostring(expected, length) << endl
//~ << " actual: " << tostring(testvals, length) << endl
//~ << endl;
//~ assert(listsAreEqual(testvals, expected, length));
return 0;
}