C#Scripting [SOLVED]: How does the following quicksort method works?

C#Scripting [SOLVED]: How does the following quicksort method works?

Home Forums Scripting C# Tutorials C#Scripting [SOLVED]: How does the following quicksort method works?

Viewing 2 posts - 1 through 2 (of 2 total)
  • Author
    Posts
  • #132772

    Cloudy Point
    Keymaster

    QuestionQuestion

    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 :

    • Why do we recurse only one side of the pivot after partitionning ? (depending the result of the if (j - left <= right - i) )
    • Why do we have a do { ... } while (left < right) over the whole thing ? Is it because we recurse only one side of the pivot as suggested above ?
    • Why is there a if (i < j) conditional test before the swap ? Isn’t the break; statement before enough?

    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);
        }
    }
    

    #132773

    Cloudy Point
    Keymaster

    Accepted AnswerAnswer

    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

    Source: https://stackoverflow.com/questions/44587043/how-does-the-following-quicksort-method-works
    Author: MBo
    Creative Commons License
    This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Viewing 2 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic.