Revisions to Hoare partitioning scheme in Quicksort

Instead of the current Wikipedia page which has become incompatible with my answer right now, refer to the version of that Wikipedia page when my answer was written.

Source Link

edited May 22, 2021 at 17:20

John L.

39.1k
4
34
91

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.

Correct minor typos.

Source Link

edited Sep 27, 2018 at 9:54

John L.

39.1k
4
34
91

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last threetwo lines of code is how to determine the index that will be used by the fistthat first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one split positionsplitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go throughover that problem closely.

"The devil is in the details" Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last three lines of code is how to determine the index that will be used by the fist two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one split position is returned when two indices iand j crosses, there is no way to be symmetric!

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go through that problem closely.

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.

Explicitly confirm one of OP's findings and invalidate another.

Source Link

edited Sep 26, 2018 at 18:24

John L.

39.1k
4
34
91

"The devil is in the details" Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last three lines of code is how to determine the index that will be used by the fist two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

WhenHowever, as mentioned by OP, the above version with its middle line of code changed to the Wikipedia page says "there are many variantspivot = A[hi] will run into an infinite loop if given an array of this algorithm, formore than one element whose unique largest element is its last element. A simple example, selecting pivot from A[hi] instead of A[lo]", it means the following variantsuch an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one split position is returned when two indices iand j crosses, there is no way to be completely symmetric!

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go through that problem closely.

"The devil is in the details" Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last three lines of code is how to determine the index that will be used by the fist two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one split position is returned when two indices iand j crosses, there is no way to be completely symmetric!

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". In fact, that problem is written in great detail in order to prove its correctness.

"The devil is in the details" Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last three lines of code is how to determine the index that will be used by the fist two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one split position is returned when two indices iand j crosses, there is no way to be symmetric!

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go through that problem closely.

Source Link

created Sep 26, 2018 at 8:08

John L.

39.1k
4
34
91

Loading

Stack Exchange Network

Return to Answer