I need to repeat the quick insertion sort from Knuth's book, but it only sorts an array with 16 elements. I'm guessing the problem is due to argument passing on the stack. I need the code structure to remain like this
void quickSort(vector<int>& arr) {
int left, right;
int M = 16;
SortQ_stack* stack = nullptr;
sortQ_push(&stack, 0, arr.size() - 1);
while (stack != nullptr) {
sortQ_pop(&stack, left, right);
if (right - left + 1 <= M && right - left + 1 > 1) {
//Q9 сортировка простыми вставками
sortS(arr, left, right);
return;
}
int K = arr[left];
int i = left;
int j = right + 1;
while (true) {
while (++i < j && arr[i] < K) {}
while (i - 1 < --j && K < arr[j]) {}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
if (left != j)
{
arr[left] = arr[j];
arr[j] = K;
}
break;
}
}
if (right - j > j - left) {
sortQ_push(&stack, j + 1, right);
right = j - 1;
}
else if (j - left > right - j) {
sortQ_push(&stack, left, j - 1);
left = j + 1;
}
else {
if (left < right) {
sortQ_push(&stack, j + 1, right);
sortQ_push(&stack, left, j - 1);
}
}
}
}
For example original array: 384 356 316 535 438 148 613 973 563 486 467 235 627 668 652 470 196 884 337 659 703 422 287 580 446 860 895 515 685 795 546 969 151 763 505 489 811 118 462 375 505 830 510 132 498 163 503 595 947 741 254 651 163 441 231 509 302 127 924 887 822 471 856 873 234 362 363 946 380 726 321 785 556 732 818 955 795 321 550 742 962 704 394 126 146 526 535 348 553 460 236 375 831 993 249 966 355 513 912 635
Uncorrectly sorted array:
151 356 316 355 249 148 375 236 348 146 126 235 321 321 380 363 196 362 337 234 127 302 287 231 163 254 163 132 375 118 384 446 438 460 505 489 486 467 462 394 505 470 510 471 498 422 503 509 441 513 515 526 535 535 553 550 546 556 563 580 595 613 627 635 651 652 659 668 685 703 704 726 732 741 818 785 795 830 763 742 856 822 831 795 811 860 962 955 946 884 873 887 924 912 895 966 947 969 993 973
I need this to work correcly on 100, 500, 1000, 5000 arrays
My stack implementation
struct SortQ_stack {
int left;
int right;
SortQ_stack* next;
};
void sortQ_push(SortQ_stack** top, int l, int r) {
SortQ_stack* new_node = new SortQ_stack();
new_node->left = l;
new_node->right = r;
new_node->next = *top;
*top = new_node;
}
void sortQ_pop(SortQ_stack** top, int& l, int& r) {
if (*top == nullptr) {
l = -1;
r = -1;
return;
}
l = (*top)->left;
r = (*top)->right;
SortQ_stack* temp = *top;
*top = (*top)->next;
delete temp;
}
There are a few issues in your code:
You shouldn't return after having called sortS, as there might be more ranges to sort on the stack.
As you start each iteration with a pop from the stack, it makes no sense to end the loop's iteration by setting left or right (as you do in the if... else if blocks). These values are immediately overwritten by what you pop from the stack. However, looking at how you decide to put the largest partition on the stack, and want to continue with the remaining partition (avoiding as much as possible to use the stack), I think you wanted to avoid stacking two partitions only to pop one of them immediately. This could be seen as a waste of stack space. But if that is the case, you should actually not pop a partition from the stack at the start of the loop, but only do that when you have dealt with a partition that cannot be split anymore. This is for example the case when you have called sortS: at that point the current partition is completely sorted and needs no more subdivisions. That's the moment to pop a next partition from the stack.
I didn't understand why at the end of the loop you have a special treatment for the case where the two partitions are equal in size. In light of the above point, you should never have to push two partitions on the stack (although that would be the way to do it if you start the iteration with a pop, but you have to make up your mind which way to go).
Not a problem, but:
The second part of the condition if (right - left + 1 <= M && right - left + 1 > 1) could be dropped if you make sure your insertion sort sortS will work well with left/right arguments that violate this second condition.
As to the testing your quicksort code, I would suggest to reduce the size of the input, and to set M to 2: the insertion sort part should not get a big role in such tests.
Here is the correction of your code:
void quickSort(vector<int>& arr) {
int left = 0, right = arr.size() - 1; // Don't use stack yet
// Set M to a low value until you are certain quickSort works perfectly
int M = 2;
// Start with an empty stack to save stack space
SortQ_stack* stack = nullptr;
// As a consequence the loop condition involves left/right
while (right > left || stack) {
if (right <= left) { // Only pop when nothing to sort in current range
sortQ_pop(&stack, left, right);
}
if (right - left + 1 <= M) { // Simplified condition
//Q9 Sorting with simple inserts
sortS(arr, left, right);
left = right; // Trigger a pop in next iteration
continue; // Don't return!!
}
int K = arr[left];
int i = left;
int j = right + 1;
while (true) {
while (++i < j && arr[i] < K) {}
while (i - 1 < --j && K < arr[j]) {}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
if (left != j)
{
arr[left] = arr[j];
arr[j] = K;
}
break;
}
}
if (right - j > j - left) {
if (right > j + 1) { // Only push windows larger than 1
sortQ_push(&stack, j + 1, right);
}
right = j - 1;
}
else { // There should be no other cases besides this one
if (j - 1 > left) { // Only push windows larger than 1
sortQ_push(&stack, left, j - 1);
}
left = j + 1;
}
}
}