0

Welcome, I have to code Quicksort Lomuto and Hoare variation in C++ using MinGW.

So, I have done it. Algorithms works fine for arrays[N] where N is small number like 5, 20, 100 but I need to do it on N = 200 000. And there is exception. I don't know why. Other algorithms(Insertion, Selection, Heapsort etc. works fine for N = 200 000).

Here is my code:

int PartitionLomuto(int A[], int p, int r)
{
    int x = A[r],
    i = p - 1,
    temp;

    for (int j = p; j <= r - 1; j++)
        if (A[j] <= x) {
            i++;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
        temp = A[i + 1];
        A[i + 1] = A[r];
        A[r] = temp;
        return i + 1;
}

void Lomuto (int A[], int p, int r)
{
    if (p < r) {
        int q = PartitionLomuto(A, p, r);
        Lomuto(A, p, q - 1);
        Lomuto(A, q + 1, r);
    }
}

//* **************************************************

int PartitionHoare(int A[], int p, int r)
{
    int x = A[p],
    i = p,
    j = r,
    temp;

    while(true) {
        while(A[j] > x)
            j--;
        while(A[i] < x)
            i++;
        if(i < j) {
            temp = A[i]; 
            A[i] = A[j];
            A[j] = temp;
            i++;
            j--;
        }
        else
            return j;
    }
}

void Hoare(int A[], int p, int r)
{
    if(p < r) {
        int q = PartitionHoare(A, p, r);
        Hoare(A, p, q);
        Hoare(A, q + 1, r);
    }
}

I'm creating arrays in that way:

int const arraySize = 200000;

int *ascending = new int[arraySize],
    *descending = new int[arraySize],
    *random = new int[arraySize];

And call function in that way:

Hoare(random,0, arraySize - 1);

Exception is in Partition function.

I really don't know what is going. I think algorithm is written right.

David Ferenczy Rogožan
  • 23,966
  • 9
  • 79
  • 68
Nerf
  • 938
  • 1
  • 13
  • 30
  • Have you considered what the error message is telling you? That the stack is overflowing? How deep is the sort going and is this due to a bug or due to the data? Have you tried enlarging the stack? – W.Prins Nov 16 '15 at 13:23
  • I don't know how do it. I can't use IDE only notepad and console. – Nerf Nov 16 '15 at 13:24
  • http://stackoverflow.com/questions/3557691/increase-stack-size-when-compiling-with-mingw – W.Prins Nov 16 '15 at 16:27

0 Answers0