The algorithm sorts a table with random numbers per 100 thousand, 500 thousand, 1 million, but when sorting an already sorted table or a table back sorted, it throws a Stack Overflow exception. I know that this is not enough memory, but how can I solve this problem?

#include "stdafx.h" #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <windows.h> void quicksort(int *A, int p, int r); int partition(int *A, int p, int r); //int A[100000]; int A[500000]; //int A[1000000]; //int B[100000]; //int B[500000]; //int B[1000000]; //int C[100000]; //int C[500000]; //int C[1000000]; int main() { srand(time(NULL)); int length = 500000; for (int i = 0; i < length; i++) { A[i] = i; //printf("%d ", A[i]); } /*for (int i = 0; i < length; i++) { B[i] = i; //printf("%d ", B[i]); }*/ /*for (int i = length-1; i >= 0; i--) { C[i] = i; printf("%d ", C[i]); }*/ float start = GetTickCount(); quicksort(A, 0, 499999); float finish = GetTickCount(); float result = (finish - start) / 1000; printf("\n losowa (seconds): %f", result); getchar(); } void quicksort(int *A, int p, int r) { float start = GetTickCount(); int q; if (p < r) { q = partition(A, p, r); quicksort(A, p, q - 1); quicksort(A, q + 1, r); float finish = GetTickCount(); float result = (finish - start) / 1000; } } int partition(int *A, int p, int r) { int i, j, x, tmp; x = A[r]; i = p - 1; for (j = p; j <= r - 1; j++) { if (A[j] <= x) { i++; tmp = A[j]; A[j] = A[i]; A[i] = tmp; } } tmp = A[i + 1]; A[i + 1] = A[r]; A[r] = tmp; return i + 1; }

    3 answers 3

    how to solve this problem?

    Use a non-recursive implementation of QuickSort. There are a lot of detailed source code analysis on C, for example, here .

    (and maybe even think about a different algorithm, not quicksort, because the example is not very clear: we are talking about real data or a learning example)

    • And what is the bad quicksort? - avp
    • @avp, maybe the answer is known by the one who claims that he is bad? - PinkTux
    • So you write - "and maybe even think about a different algorithm, not quicksort" - avp
    • @avp, but not "quicksort is bad." How often do you have to sort a million ints? To me - never (more precisely, it is necessary to sort millions by integer keys, but at this level let the database be puffed up). And here, for example, to build trees for further search on them, and not only on numeric keys, and even on composite keys - often. In general, for different purposes, different paths can be. Not to mention the fact that even if they are bare ints, but a couple of dozen of them, then they insert them. It is even strange that such things have to be explained. - PinkTux
    • Indeed. It is better to explain the other (related to the question). Namely, how to improve the algorithm used by the vehicle so that it starts working. The algorithm for your link (whether it is recursive or not) works because of this - // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub . It is also advisable to consider the algorithm for selecting a separating element ( pivot ). Now the vehicle has such a choice that for an ordered array it will be O (n ^ 2) time, not O (n log n). You can also mention the transition to a simpler sorting algorithm, when the sorted segment becomes short. Etc. - avp

    Offhand several options:

    1. Increase the size of the stack used (see compiler keys)
    2. Reduce the number of arguments passed (they just shove the call stack) - in your case, the obvious candidate is the int *a parameter - for example, you can make it global
    3. Shoot all parameters into a dynamic array of type Stack and retrieve them manually

      After q = partition(A, p, r); see which of the sub-arrays is shorter and continue recursion from it

       if (q - 1 - p < r - q + 1) { quicksort(A, p, q - 1); quicksort(A, q + 1, r); } else { quicksort(A, q + 1, r); quicksort(A, p, q - 1); }