Modify the program in the QuickSort.zip Zip file to implement the functions for
ID: 3539571 • Letter: M
Question
Modify the program in the QuickSort.zip Zip file to implement the functions for the quick
sort algorithm. When your functions are finished, the program will sort the list of strings in alphabetical
order. The quickSort() function will call the partition() function and the partition function will
call the swapItem() function. Your program must use these functions.
/**
* QuickSort.cpp - Implementation and test driver for the quick sort
* algorithm.
*
*
*/
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void quickSort(string list[], int first, int last);
int partition(string list[], int first, int last);
void swapItem(string list[], int first, int second);
void printItems(string list[], int length);
int main(int argc, char **argv)
{
string starGateCharacters[] = {
"O'Neill", "Mitchell", "Carter", "Teal'C", "Daniel Jackson",
"Vala", "Gen. Landry", "Gen. Hammond", "Jonas", "Dr. Fraiser",
"Col. Sheppard", "Dr. McKay", "Teyla", "Ronon", "Dr. Keller",
"Dr. Beckett", "Richard Woolsey", "Elizabeth Weir",
"Col. Caldwell", "Lt. Ford"
};
int numberOfCharacters = 20;
// Print the unsorted items
cout << "Items unsorted:" << endl;
printItems(starGateCharacters, numberOfCharacters);
// Sort the items
quickSort(starGateCharacters, 0, numberOfCharacters-1);
// Print the sorted items
cout << "Items sorted:" << endl;
printItems(starGateCharacters, numberOfCharacters);
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
void quickSort(string list[], int first, int last)
{
// TODO: Implement the details of this function.
return;
}
int partition(string list[], int first, int last)
{
// TODO: Implement the details of this funciton.
return 0;
}
void swapItem(string list[], int first, int second)
{
// TODO: Implement the details of this funciton.
}
void printItems(string list[], int length)
{
for (int i=0; i < length; i++)
{
cout << list[i] << endl;
}
cout << endl;
return;
}
Explanation / Answer
* algorithm.
*
*
*/
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void quickSort(string list[], int first, int last);
void partition(string list[], int first, int last);
void swapItem(string list[], int &first, int &second);
void printItems(string list[], int length);
int main(int argc, char **argv)
{
string starGateCharacters[] = {
"O'Neill", "Mitchell", "Carter", "Teal'C", "Daniel Jackson",
"Vala", "Gen. Landry", "Gen. Hammond", "Jonas", "Dr. Fraiser",
"Col. Sheppard", "Dr. McKay", "Teyla", "Ronon", "Dr. Keller",
"Dr. Beckett", "Richard Woolsey", "Elizabeth Weir",
"Col. Caldwell", "Lt. Ford"
};
int numberOfCharacters = 20;
// Print the unsorted items
cout << "Items unsorted:" << endl;
printItems(starGateCharacters, numberOfCharacters);
// Sort the items
quickSort(starGateCharacters, 0, numberOfCharacters-1);
// Print the sorted items
cout << "Items sorted:" << endl;
printItems(starGateCharacters, numberOfCharacters);
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
void quickSort(string list[], int first, int last)
{
partition(list,first,last);
return;
}
void partition(string list[], int first, int last)
{
int i = first, j = last;
string pivot = list[abs((first + last) / 2)];
/* partition */
while (i <= j) {
while (list[i] < pivot)
i++;
while (list[j] > pivot)
j--;
if (i <= j)
swapItem(list,i,j);
}
if (first < j)
quickSort(list, first, j);
if (i< last)
quickSort(list, i, last);
return ;
}
void swapItem(string list[], int &first, int &second)
{
string tmp = list[first];
list[first] = list[second];
list[second] = tmp;
first++;
second--;
}
void printItems(string list[], int length)
{
for (int i=0; i < length; i++)
{
cout << list[i] << endl;
}
cout << endl;
return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.