I've written a flexible quicksort module capable of taking a vector reference pass, cloning it, altering the clone and swapping with the original to print the list. For the most part, this works wonderfully, except for one thing.
Occasionally, it gets numbers wrong. Not all the time. If I give it five random elements (Between 1 and 100) and tell it to sort, around the sixth time I ran it it'd have a number wrong. If I gave it 5000 elements and ran it, it'd have quite a few wrong. I've stepped through the program by hand, writing down the changes on paper step by step, and can't find the error. Mind giving me a hand?
$ cat -n quicksort.cpp
1
2 #include <iostream>
3 #include <vector>
4 using namespace std;
5 /*
6 The quick-sort algorithm is fairly simple. I've set up this module to be passed a vector reference, where it will act directly upon the vector rather than having to pass information back and forth to the calling class. There are two ends, L and R, which correspond to the ends of the vector and can move accordingly to shrink the line being worked on. Each time it does, a new mid-point is determined, and the process continued again. This module is designed to be flexible, and can handle any sized (Float) vector.
7
8 */
9
10 void QuickSort(vector<float>* RawData, int Begin, int End) // The overloaded version of QuickSort, designed for re-parameterization.
11 {
12
13 int Low; // The left end.
14 int High; // The right end.
15 int Pole; // The pivot.
16 int Size=RawData->size(); // Get the size of the vector to be altered.
17 vector<float> DataRestructure(Size); //A new vector is called up to receive the incoming data off of the pointer
18 DataRestructure=*RawData; // The copy is made.
19 Low=Begin;
20 High=End;
21 Pole=(High+Low)/2;
22 // Intial Parameters are set.
23
24 do // Continue so long as Low and High haven't traded places and crossed each other over the pole. This is where the Cross happens, Low and High moving past each other.
25 {
26 while (DataRestructure[Low] < DataRestructure[Pole]) // Move towards Pole until find a number out of place.
27 {
28 Low++; // Bump bump.
29 }
30 while (DataRestructure[High]>DataRestructure[Pole]) // Move towards Pole until find a number out of place.
31 {
32 High--; // Dump dump.
33 }
34 if (Low<=High) // So long as they haven't crossed yet, swap the results of the above two bumps and dumps.
35 {
36
37 cout << DataRestructure[High] << " - " << DataRestructure[Low] << " to be swapped - " << endl;
38 swap(DataRestructure[High],DataRestructure[Low]);
39 cout << DataRestructure[High] << " - " << DataRestructure[Low] << " has been swapped - DONE" << endl << endl;
40 High--;
41 Low++;
42 }
43 } while (Low<=High);
44 if (Begin < High) // Are there still things below High after the cross? If so, drop and keep repeating.
45 {
46
47 cout << " Begin < High " << endl;
48 QuickSort(&DataRestructure, Begin, High);
49 }
50 if (Low < End) // Are there still things above Low after the cross? If so, bounce up and keep repeating.
51 {
52 cout << " Low < End " << endl;
53 QuickSort(&DataRestructure, Low, End);
54 }
55
56 RawData->swap(DataRestructure); // Return the sorted vector back to the origin.
57 }
58
59 void QuickSort(vector<float>* RawData) // Takes the pointer reference to the vector to be sorted, rather than passing the entire vector back and forth. This version is overloaded to accept the re-parameters.
60 {
61
62 int Begin; // The left most end.
63 int End; // The right most end.
64 int Low; // The left end.
65 int High; // The right end.
66 int Pole; // The pivot.
67 int Temp; // The number holder.
68 int Size=RawData->size(); // Get the size of the vector to be altered.
69 //--------------------------------------------------------------------------------------
70 // int TEST=0; // TESTER
71 //----------------------------------------------------------------------------------------
72 vector<float> DataRestructure(Size); //A new vector is called up to receive the incoming data off of the pointer
73 DataRestructure=*RawData; // The copy is made.
74 Begin=0;
75 End=Size-1;
76 Low=Begin;
77 High=End;
78 Pole=(Low+High)/2;
79 // Intial Parameters are set.
80 do // Continue so long as Low and High haven't traded places and crossed each other over the pole. This is where the Cross happens, Low and High moving past each other.
81 {
82 //-----------------------------------------------------------------------------------------------
83 // TEST++;
84 //----------------------------------------------------------------------------------------------
85
86 while (DataRestructure[Low] < DataRestructure[Pole]) // Move towards Pole until find a number out of place.
87 {
88 Low++; // Bump bump.
89
90 }
91 while (DataRestructure[High]>DataRestructure[Pole]) // Move towards Pole until find a number out of place.
92 {
93 High--; // Dump dump.
94
95 }
96 if (Low<=High) // So long as they haven't crossed yet, swap the results of the above two bumps and dumps.
97 {
98
99 cout << DataRestructure[High] << " - " << DataRestructure[Low] << " to be swapped - " << endl;
100 swap(DataRestructure[High],DataRestructure[Low]);
101 cout << DataRestructure[High] << " - " << DataRestructure[Low] << " has been swapped - DONE" << endl << endl;
102 High--;
103 Low++;
104 }
105 } while (Low<=High);
106 if (Begin < High) // Are there still things below High after the cross? If so, drop and keep repeating.
107 {
108 cout << " Begin < High " << endl;
109 QuickSort(&DataRestructure, Begin, High);
110 }
111 if (Low < End) // Are there still things above Low after the cross? If so, bounce up and keep repeating.
112 {
113 cout << " Low < End " << endl;
114 QuickSort(&DataRestructure, Low, End);
115 }
116
117 RawData->swap(DataRestructure); // Return the sorted vector back to the origin.
118 }
119
120
121 #if __INCLUDE_LEVEL__ < 1
122
123 #include <iostream>
124 #include <vector>
125 using namespace std;
126 /*
127 This entire section is devoted to testing the flexible module above.
128 */
129 int main()
130 {
131 int SizeOfThread=20; // Determines how big the test thread will be.
132 srand((unsigned)time(0)); // Seeding random number generator.
133 vector<float> test(SizeOfThread);
134 for (int i=0; i<SizeOfThread; i++)
135 {
136 test[i]=rand()%100+1;
137 }
138 cout << "Before the de-scramble: " << endl;
139 for (int i=0;i<SizeOfThread;i++)
140 {
141 cout << test[i] << endl;
142 }
143 QuickSort(&test);
144
145 cout << "After de-scrambler:" << endl;
146 for (int i=0;i<SizeOfThread;i++)
147 {
148 cout << test[i] <<endl;
149 }
150 return 0;
151 }
152
153 #endifSo. Where is my reiteration ending too quickly? I did a 'quicksort' search through the forum menu, but didn't really find anything like what I was seeing.
