This repository was archived by the owner on Jan 27, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.cpp
More file actions
147 lines (123 loc) · 4.7 KB
/
Copy pathQuickSort.cpp
File metadata and controls
147 lines (123 loc) · 4.7 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include "QuickSort.h"
#include <fstream>
using namespace std;
//-------------------------------------------------------------------------------------------------
// Function Name: QuickSort
// Purpose: QuickSort constructor initializes the sort table
// Parameters: int* theValues in the unsorted list
// Returns: none
// Pre-conditions: none
// Post-conditions: theList contains a pointer to the unsorted list
//-------------------------------------------------------------------------------------------------
QuickSort::QuickSort(int theCount, int* theList)
{
this->theCount = theCount;
this->theList = theList;
}
//-------------------------------------------------------------------------------------------------
// Function Name: ~QuickSort
// Purpose: ~QuickSort destructor performs house cleaning when the class is destroyed
// Parameters: none
// Returns: none
// Pre-conditions: none
// Post-conditions: none
//-------------------------------------------------------------------------------------------------
QuickSort::~QuickSort()
{
if (theList != nullptr)
delete[] theList;
theCount = 0;
theList = nullptr;
}
//-------------------------------------------------------------------------------------------------
// Function Name: sort
// Purpose: sort the list using the Quick Sort algorithm
// Parameters: none
// Returns: none
// Pre-conditions: theList contains a valid pointer to an array of ints
// Post-conditions: theList is sorted
//-------------------------------------------------------------------------------------------------
void QuickSort::sort()
{
if (theCount <= 1 || theList == nullptr)
return;
// sort the whole list starting with the first element through the last element
internalSort(0, theCount - 1);
}
//-------------------------------------------------------------------------------------------------
// Function Name: internalSort
// Purpose: internalSort is recursively called using a divide and conquer strategy to
// sort the list
// Parameters: int left is the left starting position in the list
// int right is the right starting position in the list
// Returns: none
// Pre-conditions: theList contains a valid pointer to an array of ints
// Post-conditions: theList is sorted
//-------------------------------------------------------------------------------------------------
void QuickSort::internalSort(int left, int right)
{
// chose the pivot point to be the middle element (left + (right - left) /2)
int pivotIndex = left + (right - left) / 2;
int pivotValue = theList[pivotIndex];
int tmpLeft = left;
int tmpRight = right;
// partition the values with:
// those smaller than the pivot to the left
// those larger than the pivot to the right
while (left <= right)
{
// skip values that are less than the pivot
while (theList[left] < pivotValue)
{
left++;
}
// skip values that are greater than the pivot
while (theList[right] > pivotValue)
{
right--;
}
// swap the values if the left hasn't crossed the right
if (left <= right)
{
swap(theList[left], theList[right]);
left++;
right--;
}
}
// continue to recursively call internalSort while the left hasn't crossed the pivot point
if (tmpLeft < right)
{
internalSort(tmpLeft, right);
}
// continue to recursively call internalSort while the right hasn't crossed the pivot point
if (tmpRight > left)
{
internalSort(left, tmpRight);
}
}
//-------------------------------------------------------------------------------------------------
// Function Name: saveList
// Purpose: saves the list (sorted or unsorted) to the specified filename
// Parameters: const char* filename is the filename to write the list to
// Returns: true if successful, false otherwise
// Pre-conditions: filename is not null
// Post-conditions: none
//-------------------------------------------------------------------------------------------------
bool QuickSort::saveList(const char* filename)
{
if (filename == nullptr)
return false;
ofstream outFile(filename);
//outFile.open(filename);
if (!outFile.good())
return false;
if (theList == nullptr)
{
theCount = 0;
outFile << "theList was null. nothing to save." << endl;
}
for (int x = 0; x < theCount; x++)
outFile << theList[x] << endl;
outFile.close();
return true;
}