1

I am trying to implement a quicksort algorithm with Hoare partioning which can work with a large set of array. It works with small size arrays however when creating a large array the application stops working. Can anyone help?

The implementation looks as followed: QuickSort.h

void SerialQuicksort(T* first, T* last, T* myArray, int size) {
    if (last - first>1) {
        T* mid = ModifiedHoare(myArray, first, last);
        SerialQuicksort(first, mid+1, myArray, size);
        SerialQuicksort(mid+1, last, myArray, size);
    }
}

Partitioning function:

    int* ModifiedHoare(int* a, int* p, int* r)
{
    if (*p>*r)
        swapp(p, r); // Sentinel at both ends
        int x = *p; // x stores the pivot and location p is vacant now.
        while (1)
        {
            do{
                *r--;
            } while (*r>x); // search the smaller   element in right
                // portion.
                *p = *r; // location r is vacant now.
                do{
                    *p++;
                } while (*p<x); // search the larger element in left portion.
                    if (p<r)
                        *r = *p; // location p is vacant now.
                    else{
                    if (*(r + 1) <= x)
                        r++;
                    *r = x;
                    return r; // return the location of the pivot
                }
        }
}

inline void swapp(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

Test - Main

#define SIZE 20000
int* myArray = new int[SIZE];
for (int i = 0; i < SIZE; i++)
{
    *(myArray + i) = rand();
}

parallelQuick.SerialQuicksort(&myArray[0], &myArray[SIZE-1], myArray, SIZE);

Output on screen: enter image description here

When debugging the application an exception appears with the following:

Access violation writing location 0x00140F64

#define SIZE 356

Number of calls Exception popup window

Voicu
  • 56
  • 5
user2439427
  • 131
  • 1
  • 9
  • 1
    *"... however when creating a large array the application stops working."* - Can you [edit] your question to be more specific... How large of an array? What do you mean *"stops working"*? Any errors? – Jonny Henly Feb 15 '17 at 17:34
  • I tested with different array sizes. The current test is with an array of size 20000 elements. I have updated the post with an image of the output. Basically what is written is that the application is stopped working simular to this image: https://www.google.dk/search?q=exe+stops+working&biw=1680&bih=880&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjm7-jk05LSAhXFjCwKHenHBboQ_AUICCgB#imgrc=JpHhSEC9Pyy5SM: – user2439427 Feb 15 '17 at 17:51
  • 3
    @user2439427 If it doesn't work with large arrays, it probably is broken for small arrays also, just that you haven't noticed it yet. Also, 20000 is **not** large. – PaulMcKenzie Feb 15 '17 at 18:18
  • I have tested different sizes below 1000 which is not a large array but it works every time. Everytime i try to make the array a bit larger it cannot handle it. – user2439427 Feb 15 '17 at 18:27
  • 1
    You could have also posted an [mcve] just like [this one](http://ideone.com/VIKsol). Running that program under Visual Studio reveals a stack overflow error. – PaulMcKenzie Feb 15 '17 at 18:28
  • Also, [this quicksort program](http://ideone.com/HWE3A6) using [this implementation that uses recursion](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) sorts correctly. So again, you have a bug in that you are excessively calling your recursive function, even for the cases you say "work correctly". – PaulMcKenzie Feb 15 '17 at 18:35
  • http://ideone.com/1R1MVL – user2439427 Feb 15 '17 at 18:37
  • @user2439427 -- Doesn't matter. You have a bug that was exposed by the large number. A recursive quick sort should never bomb out at 20,000. That means that you are erroneously calling your recursive function too many times, even for the cases that work. – PaulMcKenzie Feb 15 '17 at 18:38
  • Obviously something os wrong which is why i seek for help by asking a question in here since i cannot solve it myself and i have been stuck quite a while now. – user2439427 Feb 15 '17 at 18:41
  • why not press 'break' and see what line its failing on. Or check the box 'break when this exception is thrown' and run it again. VS is trying to help you – pm100 Feb 15 '17 at 18:51
  • `SerialQuicksort(first, mid+1, myArray, size);` looks like a bug. You should probably use `mid-1` instead. – rlbond Feb 15 '17 at 18:52
  • did not test but at the first glance this seems wrong `SerialQuicksort(first, mid+1, myArray, size); // mid -1 SerialQuicksort(mid+1, last, myArray, size);` – LZR Feb 15 '17 at 18:53
  • @user2439427 You need to debug your code. The immediate issue is that you are blowing out the stack by calling your function too many times. Observe what you're doing when you choose your first and mid. Also, you don't need to pass `myArray` or `SIZE` to any of your functions. Note that both of these parameters are not used at all. All you need is the start and end of the range you're sorting. – PaulMcKenzie Feb 15 '17 at 18:54
  • `*r--;` I don't think this does what you think it does. – rlbond Feb 15 '17 at 18:55
  • I did debug and yet i am still stuck. I believe it is because the recursion is so deep but I dont know how to fix it. The Error when debygging is stackoverflow – user2439427 Feb 15 '17 at 20:41
  • Your program has not a single comment. Add the appropriate comments, explaining what EXACTLY each function does, and what each parameters EXACTLY means. Without comments, it is not surprising it doesn't work. And never use parameters like "a", "r", "p". Names should be meaningful. And fix the indentations. Your code is written so bad, that I would be surprised if it had no bug. – user31264 Feb 16 '17 at 02:10
  • One obvious bug: if last-first==1, your SerialQuicksort does nothing. Instead, it should swap two elements of the array if neccessary. – user31264 Feb 16 '17 at 02:13

1 Answers1

0

You could increase the stack size, by stetting stack reserve size (in configuration properties > linker > system) to a higher value, but this won't help if the recursion is too deep.

user3345850
  • 141
  • 2
  • 11