CODEWITHSUNDEEP
c#algorithmlinqquicksortpartitioning
tigrou
tigrou

Reputation: 4526

How does the following quicksort method works?

I wrote my own Quicksort method for educational purposes. In order to improve it, I took a look at .NET source code to see how to LINQ OrderBy() method is implemented.

I found the following Quicksort method : 

void QuickSort(int[] map, int left, int right) {
    do {
        int i = left;
        int j = right;
        int x = map[i + ((j - i) >> 1)];
        do {
            while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
            while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
            if (i > j) break;
            if (i < j) {
                int temp = map[i];
                map[i] = map[j];
                map[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i) {
            if (left < j) QuickSort(map, left, j);
            left = i;
        }
        else {
            if (i < right) QuickSort(map, i, right);
            right = j;
        }
    } while (left < right);
}

I am trying to understand the inner workings. AFAIK it looks very similar to Hoare partition scheme but with some slight optimisations.

What is unclear to me is :

In comparison, here is how my actual implementation Quicksort looks (straight implementation of Hoare partition scheme)

void QuickSort(int[] map, int left, int right)
{
    if (left < right)
    {
        int i = left - 1;
        int j = right + 1;
        int x = map[left + ((right - left) >> 1)];

        while (true)
        {
            do { i++; } while (Compare(map[i], x) < 0);
            do { j--; } while (Compare(map[j], x) > 0);

            if (i >= j) break;

            int temp = map[i];
            map[i] = map[j];
            map[j] = temp;
        }

        QuickSort(map, left, j);
        QuickSort(map, j + 1, right);
    }
}

Upvotes: 3

Views: 127

Answers (1)

MBo
MBo

Reputation: 80327

Why do we recurse only one side of the pivot after partitionning ? (depending the result of the if (j - left <= right - i) )

To minimize recursion depth (and stack usage). When we treat larger partition as soon as possible and do recursion only for smaller partition, depth does not rise above log(n)

Why do we have a do { ... } while (left < right) over the whole thing ?

Items before left and after right are sorted, so these indexes meet when all array is sorted

Why is there a if (i < j) conditional test before the swap ?

Just to avoid unnecessary swap for equal indexes

Upvotes: 3

Related Questions