-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlab09.cpp
More file actions
90 lines (71 loc) · 1.79 KB
/
lab09.cpp
File metadata and controls
90 lines (71 loc) · 1.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
// Name: Eric Lepki
// Date: 04/02/18
// Class: 2380
// Semester: Spring 18
//
// Program Name: Lab 09
// File Name: lab09.cpp
// Program Description: Sorts char in strings using Quicksort
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
#include<iostream>
#include<string>
using namespace 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 = high;
int index = low;
char pivot;
//base case if only one element
/*if (low == 0) {
QuickSort(input, low, high);
}*/
//choose pivot as middle element
pivot = input[(low + high) / 2];
//swap pivot with index
pivot = input[index];
input[index] = pivot;
//execute quicksort loop
int temp;
while (index <= smallindex) {
while (input[index] < pivot) {
index++;
}
while (input[smallindex] > pivot) {
smallindex--;
}
if (index <= smallindex) {
temp = input[index];
input[index] = input[smallindex];
input[smallindex] = temp;
index++;
smallindex--;
}
}
//swap pivot with smallindex
//recursively call each side
if (low < smallindex) {
QuickSort(input, low, smallindex);
}
if (index < high) {
QuickSort(input, index, 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;
}