3
\$\begingroup\$

I'm learning C++ and algorithms myself, and as training I had to write quicksort by myself.All feedback on coding style/clarity and concepts are welcomed!

int QuickSort(int *Array, int start, int end)//Recursive function that sorts array
{
    int Wall = start;//Variable that will hold pivot position before recursive calls and tracks indexes                 
    int Temp = 0;   //Variable used for swaping array members
    if (start < end)//Exit condition
    {
        for (int Index = start; Index < end; Index++)
        {
            if (Array[Index] <= Array[end])
            {
                Temp = Array[Wall];
                Array[Wall] = Array[Index];
                Array[Index] = Temp;
                Wall++;
            }
        }
        Temp = Array[end];
        Array[end] = Array[Wall];
        Array[Wall] = Temp;
    QuickSort(Array, start, --Wall);//Calling racursion for left of the pivot
    QuickSort(Array, ++Wall, end);//Calling recursion for right of the pivot
    }
 return 0;
}
\$\endgroup\$
  • \$\begingroup\$ The question is off-topic since it contains code known to the author to be broken (stack-overflow exception). Voting to place this question on hold until it's fixed. \$\endgroup\$ – Snowhawk Oct 25 '17 at 3:27
  • \$\begingroup\$ I don't know - a stack overflow when there are 10,000 elements? Given errors I've seen in other code here that passed muster, I wouldn't consider that a deal breaker, personally. \$\endgroup\$ – user1118321 Oct 25 '17 at 6:22
  • \$\begingroup\$ @Adler11th - why do you think it takes up too much memory? Aside from stack space, it works in-place. That seems pretty memory efficient to me. \$\endgroup\$ – user1118321 Oct 25 '17 at 6:23
  • \$\begingroup\$ I ran new tests in the evening. It's really inconsistent with results I had when I was posting this code. Now it seems to run much quicker and can handle arrays size even at 100 000(adding one more zero will cause stack overflow). Maybe its VS2017 ??IDK. However any feedback on coding itself will be welcomed. I never had any friends/co-workers which can undertand and write code thus I don't have any input on how well/bad I am doing. Thank you \$\endgroup\$ – Max Oct 25 '17 at 7:11
  • \$\begingroup\$ @Snowhawk, I believe by too much OP meant around 1MB. I wouldn't take the observations literally most of the time. Voting to leave open. Probably OP stumbled upon a very bad partition. \$\endgroup\$ – Incomputable Oct 25 '17 at 8:35
6
\$\begingroup\$

I think this is fairly impressive. I don't know if I would have done this in-place if I sat down to do this today. That said, I do see a few things you could improve.

Naming

I think your variable names could use some work. Why did you choose Wall? That name just doesn't strike me as useful in this context.

I notice that you're mixing capitals and lowercase letters for the first letter of your variables. Typically variables start with a lowercase letter and type names start with an uppercase letter. You don't necessarily have to follow that convention, but you should be consistent.

C++

The only line of code in this that differentiates it from C is the print statement, which I assume is just for debugging. If you #include <utility> you get some very useful functions. (You'll need to #include <algorithm> if you're using C++ that pre-dates C++11.) For example, std::swap() will swap 2 values for you without the need to write out 4 lines of code:

std::swap(Array[Wall], Array[index]);

does the same thing as:

int Temp = 0;   //Variable used for swaping array members
...
            Temp = Array[Wall];
            Array[Wall] = Array[Index];
            Array[Index] = Temp;

Also, you don't need std::endl where you've used it. That will flush the buffer which will slow things down. You can simply use:

std::cout << Wall << "\n";

And if you're really paranoid, you can add a single call to:

std::cout << std::endl;

after QuickSort returns;

Recursion

As you found, when you have a deeply recursive function, it can eventually eat up the entire stack if you're not careful. Luckily, you can eliminate recursion in many cases. I modified yours to remove the recursion by adding a simple std::queue and putting the ranges in the queue instead of calling back into the function. First, I made a simple struct to hold a range of indexes to sort:

struct Range {
    int start;
    int end;

    Range(int newStart, int newEnd) : start(newStart), end(newEnd) {}
};

Then I updated the function to use a std::queue and the new Range type:

void QuickSort(int* array, int start, int end)
{
    std::queue<Range>  queue;
    queue.push(Range(start, end));
    while(!queue.empty())
    {
        Range next    = queue.front();
        queue.pop();

        int start = next.start;
        int end = next.end;
        int Wall = start;
        if (start < end)
        {
            for (int Index = start; Index < end; Index++)
            {
                if (array[Index] <= array[end])
                {
                    std::swap(array[Wall], array[Index]);
                    Wall++;
                }
            }
            std::swap(array[end], array[Wall]);
            queue.push(Range(start, --Wall));
            queue.push(Range(++Wall, end));
        }
    }
}

I kept most of your code, but used std::swap and removed the recursion.

To be honest, I didn't think the performance of your version was bad at all. It seemed to work plenty fast for me.

\$\endgroup\$
  • \$\begingroup\$ Thank you! I will work on on the issues you pointed out. I ran test again and this time it was much different from what I had when I was posting this code. Idk maybe it was just VS2017 doing some wierd things which I don't understand yet. \$\endgroup\$ – Max Oct 25 '17 at 7:16
  • \$\begingroup\$ Hmm... you are correct. It used to be in <algorithm> pre-C++11, but somehow, when I went to compile my changes, I was getting an error on that line that seemed to go away with #include <stdlib.h>. Must have just been a coincidence. I will correct that. \$\endgroup\$ – user1118321 Oct 25 '17 at 16:04
  • \$\begingroup\$ I wouldn't worry too much about recursion depth, as it only scales \$O(lg(N))\$on average, \$O(N)\$ in the worst-case, which can be avoided in the OP's solution by choosing a better pivot (e.g. median as pivot, random element as pivot). However, in your solution, you'd queue up \$O(N)\$ ranges in every case (i.e. you always have a worst case), as you are basically doing a level-order traversal instead of a pre-order traversal. Maybe us a stack instead of a queue? \$\endgroup\$ – hoffmale Oct 25 '17 at 16:56
  • \$\begingroup\$ Yes, I realized at 5AM that I had intended to use a stack. Regardless, the reason I brought it up was because the OP's description made it sound like he may have been hitting a stack overflow from the recursion. That's why I mentioned it. \$\endgroup\$ – user1118321 Oct 26 '17 at 2:38
  • \$\begingroup\$ Please note that the use of queues does not solve the problem with the unbalanced partitioning, it just shifts the memory consumption from a limited stack space to a much more capacious heap. If you worry about the memory consumption in the partitioning's worst case, just push the longer partition to the stack and iterate processing the shorter one with `while(start<end){...}. In the recusive implementation: recurr with the shorter part and after return proceed with partitioning the longer one. This way the worst memory cost is kept at \$\log_2 N\$. \$\endgroup\$ – CiaPan Oct 30 '17 at 11:34
4
\$\begingroup\$

Iterators

Currently you can sort anything that uses int*. But an iterator is a data type that has the same behavior as a pointer (when used in appropriate contexts). But there are other types that are iterator; so using them makes your code much more generalized.

template<typename I>
int QuickSort(I begin, I end)

Now your sort is generalized for any type that supports iterators (a pointer can be used as an iterator into a C-Array). But you can now also sort vector's lists and any other standard container type.

Don't Declare variables before you use them

int Temp = 0;   //Variable used for swaping array members

This is declared way at the top.
You should declare variables just before you need them. This helps in the readability of the code (as I don't have to scroll back to the top of the function to find out what the code type is).

Also it prevents you wasting an instruction initializing a value that you will never use (here you init to zero but is that just a waste). If you declare at the point of usage you avoid that waste.

            int Temp = Array[Wall];      // declaration and initialization
            Array[Wall] = Array[Index];
            Array[Index] = Temp;

Also when object becomes more complex and they have constructors. Initializing them only when you need them can become a good savor of space time.

Prefer pre-increment

You seem to use post increment. This is fine when the type is an integer. But in C++ code you usually see this with iterators and here the post increment is slightly less efficient than the pre-increment.

By using pre-increment you will always have the most efficient version and when your code is altered (and it will be) the person changing it does not need to go and check all the places where you use increment and change it from post to pre.

\$\endgroup\$
4
\$\begingroup\$

Implementation

  • Since the return value 0 isn't used anywhere, why not make the return type void?
  • Inconsistent naming: Some variable names start with a capital letter, some don't.
  • Naming: Wall is even described as pivot position in the comment. Why not name it Pivot?
  • Swapping elements could be done using std::swap, or barring access to a standard library, delegated to a similar function.

Design

  • While the function length isn't too bad, the partition logic could be extracted into its own function for readability.
  • Usual C++ standard library implementations work with iterators. QuickSort could be designed to accept those.
  • QuickSort only works for elements of type int. This could be extended for other types (e.g. by using a template).
  • Usually, ranges are expected to not include the last element. end however is included into the range to be sorted. While no problem on its own, it might make sense to adhere to the usual convention. After all, which is clearer: QuickSort(vec.data(), 0, vec.size()) or QuickSort(vec.data(), 0, vec.size() - 1)?

Performance / Correctness

  • QuickSort repeatedly includes the current pivot in the recursive calls (the second recursive call, to be exact), while it doesn't have to be included. After all, we already know its final position.
  • During the partition step, QuickSort copies every element that is equal to the pivot to the first "half". These copies aren't necessary! If they are equal to the pivot, it doesn't matter if they are left or right of the pivot.
  • QuickSort uses a bad pivot: In the worst case (e.g. all elements reversed, or, thanks to the issue above, all elements equal), it's going to recurse up to depth \$O(N)\$. This, combined with a small choice of random elements, is very likely the source of your stack overflow issue (try an array of all 0s against an array with all distinct elements!). With a better choice of pivot (e.g. median, median-of-three or random) and partitioning algorithm (e.g. no copying of elements equal to the pivot), you'd never get (or at the very least, be much less likely to get) the worst case behavior.
  • The quick sort algorithm has low complexity, so it's fast for huge data sets. However, for small data sets, other sorting algorithms (even bubble sort!) can be faster. If the difference between start and end drops below that threshold, it would very likely be better for performance to use another sorting algorithm to sort that subset.
\$\endgroup\$
  • \$\begingroup\$ If they are equal to the pivot, it doesn't matter if they are left or right of the pivot. That depends on your definition of correctness. If you want your sorts to be stable then they need to be copied. This is more useful when you upgrade to a more interesting type than int but it is nice if your sort is already stable before you generalize. \$\endgroup\$ – Martin York Oct 25 '17 at 21:55
  • \$\begingroup\$ @LokiAstari: Not necessarily: you'd only need to guarantee that the position of the pivot relative to the other equal elements doesn't change. In the OPs case, that's only happening because of that specific choice of pivot and him copying all those equal elements. Both choices aren't benefiting the runtime performance (in fact, they are the reason for the stack overflows!). ... \$\endgroup\$ – hoffmale Oct 25 '17 at 22:48
  • \$\begingroup\$ @LokiAstari: ... That said, quicksort usually isn't stable (nor is it expected to) - it's strengths are \$O(log N)\$ average memory usage and \$O(N log N)\$ average runtime complexity. Making quicksort stable inherently requires it to lose at least one of those qualities (everything has its price)! Also, if you require stability, there are other established sorting algorithms that provide that within well specified parameters, e.g. mergesort. \$\endgroup\$ – hoffmale Oct 25 '17 at 22:48
  • \$\begingroup\$ Regarding the first item headed Performance / Correctness: I don't see "the" pivot included (++Wall)(, even the spelling of recursion looks correct(ed)). The way to preclude O(n) space for limits of unhandled ranges is to recurse on the smaller partition, but iterate on the larger (Sedgewick (in "Implementing Quicksort programs"?)). \$\endgroup\$ – greybeard Oct 26 '17 at 7:19
  • \$\begingroup\$ @greybeard: the pivot is included in the second call, because ++Wall only "cancels out" --Wall in the call before (so it's pointing to the pivot again). // To get \$O(log N)\$ space complexity (aka recursion depth), the partitions should be relatively even in length. If perfectly halved at each step, you'd need \$(log_2(N)\$ recursion calls. However, in case of the most uneven split (\$N - 1\$ one side, other \$0\$), you'd need \$N\$ calls total (because every call only takes 1 element from the range). \$\endgroup\$ – hoffmale Oct 26 '17 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.