Hey there. I'm working on a program that reads numbers from an input file, performs a quicksort on those numbers and sends the sorted numbers to an output file. Below is the section of code that performs the quicksort. Everything looked to be working just fine with the sorting algorithms. But when I checked one of the output files, something was off. Output file: createArray 20 True addToArray 9 True addToArray 8 True addToArray 7 True addToArray 6 True addToArray 5 True addToArray 4 True addToArray 3 True addToArray 2 True addToArray 1 True addToArray 0 True getArray 9,8,7,6,5,4,3,2,1,0 sortAll getArray 9,8,7,6,5,4,3,2,1,0 Any ideas why the initial sorting was not performed in this particular case? It should be 0,1,2,3,4,5,6,7,8,9. I can't seem to figure it out. Thanks for your help!

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

#ifndef QS_H_ #define QS_H_ #include "QSInterface.h" #include namespace std { class QS: public QSInterface { public: QS(); virtual ~QS(); bool sorted(int left, int right); void swap(int *first, int *second); void sortAll(); int medianOfThree(int left, int right); int partition(int left, int right, int pivotIndex); string getArray() const; int getSize() const; bool addToArray(int value); bool createArray(int capacity); void clear(); private: int *data, numAdds, dataSize; }; } #endif

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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164

#include "QS.h" namespace std { QS::QS() { numAdds = 0; data = NULL; dataSize = 0; } QS::~QS() { clear(); } void QS::swap(int *first, int *second) { int temp = *first; *first = *second; *second = temp; } bool QS::sorted(int left, int right) { if (right < left) { return false; } if (left == right - 1) { if (*(data + left) > *(data + right)) { swap(data + left, data + right); } return true; } else if (left == right) { return true; } else { int pivotIndex = partition(left, right, medianOfThree(left, right)); return sorted(left, pivotIndex - 1) && sorted(pivotIndex + 1, right); } } void QS::sortAll() { if (data == NULL || numAdds < dataSize || dataSize <= 0) { return; } if (sorted(0, dataSize - 1)) { return; } else { //cout << "data not sorted" << endl; } } int QS::medianOfThree(int left, int right) { if (data == NULL || left < 0 || right > (numAdds - 1) || left >= right) { return -1; } int middle = (left + right) / 2; if (*(data + middle) > *(data + right)) { swap(data + middle, data + right); } if (*(data + left) > *(data + middle)) { swap(data + left, data + middle); } if (*(data + middle) > *(data + right)) { swap(data + middle, data + right); } return middle; } int QS::partition(int left, int right, int pivotIndex) { if (left > right || !(left < pivotIndex && pivotIndex < right) || data == NULL || left < 0 || right >= numAdds || right - left < 2) { return -1; } swap(data + left, data + pivotIndex); int *up = (data + left + 1), *down = (data + right); do { while (*up <= *(data + left) && up != (data + right)) { up++; } while (*down > *(data + left) && down != (data + left)) { down--; } if (up < down) { swap(up, down); } } while (up < down); swap(data + left, down); return (down - data); } string QS::getArray() const{ if (numAdds == 0 || data == NULL || dataSize == 0) { return ""; } string result = "", intString = ""; stringstream ss; for (int i = 0; i < numAdds; i++) { ss << *(data + i); ss >> intString; ss.clear(); result += intString; if (i < numAdds - 1) { result += ","; } } return result; } int QS::getSize() const { return numAdds; } bool QS::addToArray(int value) { if (numAdds < dataSize) { *(data + numAdds) = value; numAdds++; return true; } else{ return false; } } bool QS::createArray(int capacity) { if (capacity <= 0) { return false; } data = new int[capacity]; dataSize = capacity; numAdds = 0; return true; } void QS::clear() { if (data == NULL || numAdds <= 0) { return; } delete[] data; data = NULL; numAdds = 0; dataSize = 0; } }