So I'm learning c++ and I'm extremely confused by quick sort. I've watched videos and read chapters and I'm still stumped by this assignment. The idea of the assignment is to sort a user input string with quick sort, using a middle pivot and recursion.
The main issue I'm having is the implementation of the for loop that will break the string into two parts (the less than pivot and the greater than pivot.)
This whole assignment has me lost I feel like I'm way off track. Could someone help get me going in the right direction?
#include<iostream>
#include<string>
usingnamespace std;
//Here we use quicksort to sort the string of characters
//we sort the string in place without making any copies, so
//for a call to quicksort we pass in the low and high indices
//we sort to.
void QuickSort(string &input, int low, int high)
{
//initial conditions
int smallindex = low;
int index = low;
char pivot;
//base case if only one element
if(input.size()<=1)
return;
//choose pivot as middle element
pivot=input[input.size()/2];
//swap pivot with index
swap(input[index],input[input.size()/2]);
//execute quicksort loop
for(int index;index<high;index++)
{
if(input.at(index)<pivot)
{
smallindex++;
//swap pivot with smallindex
swap(input[index],input[smallindex]);
}
}
//recursively call each side
QuickSort(input, low, smallindex - 1);
QuickSort(input, smallindex + 1, high);
}
//in main we just want to take in a string
int main()
{
string input;
cout << "Please input a string:" << endl;
//get the string
getline(cin, input);
//efficiently sort the list
QuickSort(input, 0, input.length()-1);
//print the output
cout << input << endl;
return 0;
}