Sorting arrays with Quicksort C++

Question

I am working on a projekt (for school) and one of the requirements is to sort an array. So I decided to use the quicksort. (I chose it because it is an algorithm that I don't know by now) I managed to understand how it works and I also found an option of its implementation in c++.

void quicksort(size_t v[], size_t start_pos, size_t end_pos)
{
    size_t i, j, di, dj;
    if (start_pos < end_pos)
    {
        i = start_pos, j = end_pos;
        di = 0, dj = 1;
        do
        {
            while (i < j && (v[j] > v[i] || v[j] == v[i])) i += di, j -= dj;
            if (i < j)
                std::swap(v[i], v[j]), di = (di + 1) % 2, dj = (dj + 1) % 2;
        } while (i < j);
        if (i - start_pos > 1)
            sort(v, start_pos, i - 1);
        if (end_pos - i > 1)
            sort(v, i + 1, end_pos);
    }
}

What I don't understand is... why in the last 2 if statements is used ">1"? I hope someone can clarify this for me. Thank you! :)

So you were asked to write a sort function for your project, and instead of actually writing one, you just randomly found one online, and now you want us to explain to you how it works? Did that about sum it up? — Cory Kramer
– Cory Kramer, Commented Jun 24, 2015 at 11:27
You should understand how it works not by the code but by looking into the algorithm specification. Otherwise, your question not about the algorithm but about the code you have found somewhere. — VP.
– VP., Commented Jun 24, 2015 at 11:28
This is a really weird implementation of quicksort. At the very least - it's not even recursive? What is sort? — Barry
– Barry, Commented Jun 24, 2015 at 11:31
What I don't like in the posted code: array of size_t (!?), abuse of the comma operator, delta variables di,dj which have values 0 or 1 and make the logic more complex, the code to flip the deltas di = (di+1)%2 (when a xor or a ! suffices), the weird condition (v[j] > v[i] || v[j] == v[i]) (why not >=?). — chi
– chi, Commented Jun 24, 2015 at 12:29

Captain Giraffe · Accepted Answer · 2015-06-24 11:33:31Z

3

Both calculations provides the size of the left and right subdivision respectively.

If the size is 1 or zero, that part is already sorted and doesn't need any further processing.

    if (i - start_pos > 1)  
        sort(v, start_pos, i - 1);

The sort call is only made if the range is two or more elements. As Barry points out, this should probably be

    if (i - start_pos > 1)  
        quicksort(v, start_pos, i - 1);

Victors comment is also on point.

edited Jun 24, 2015 at 11:33

answered Jun 24, 2015 at 11:28

Captain Giraffe

14.8k7 gold badges42 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

1_gd_apple · Accepted Answer · 2015-06-24 11:35:15Z

0

If you look carefully, the upper portion of the code does the arranging the array corresponding to pivot element which is indexed at i and the last two if's sort the remaining portion i.e. to the right and left of the pivot element but in case your pivot index has already reached end_pos you don't need to sort elements to right of the pivot element thus there is an if condition whether i < end_pos.

answered Jun 24, 2015 at 11:35

1_gd_apple

1

Collectives™ on Stack Overflow

Sorting arrays with Quicksort C++

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related