CODEWITHSUNDEEP
c++arraysquicksort
alfa_peste
alfa_peste

Reputation: 9

Sorting arrays with Quicksort C++

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! :)

Upvotes: 0

Views: 178

Answers (2)

1_gd_apple
1_gd_apple

Reputation: 1

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.

Upvotes: 0

Captain Giraffe
Captain Giraffe

Reputation: 14705

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.

Upvotes: 3

Related Questions