Implementing quick sort in Python - list index/infinite loop bugs

Question

I'm trying to implement quicksort in Python. I used the pseudocode found on Wikipedia here as a basis. That had do...while loops in it, so I used the

while True:
    # code
    if condition:
        break

construct to simulate it.

I have tried a lot of things like incrementing/decrementing differently or adding checks for indexes out of bounds (which the pseudocode does not have because it is not supposed to be necessary using the Hoare algorithm, at least I think so...). I always get either an IndexError or an infinite loop.

Could someone show me where I have gone wrong in implementing the algo please?

class QuickSort:

    def sort(self, data):
        if data is None:
            raise TypeError()
        n = len(data)
        if n < 2:
            return data
        self._sort(data, 0, len(data) - 1)
    
    def _sort(self, A, lo, hi):
        if lo >= 0 and hi >= 0:
            if lo < hi:
                p = self._partition(A, lo, hi)
                self._sort(A, lo, p)
                self._sort(A, p + 1, hi)

    def _partition(self, A, lo, hi):
        pivot = A[(hi + lo) // 2]
        i = lo - 1
        j = hi + 1
        while True:
            while True:
                i += 1
                if A[i] < pivot:
                    break
            while True:
                j -= 1
                if A[j] > pivot:
                    break
            if i >= j:
                return j
            A[i], A[j] = A[j], A[i]

EDIT: The reason was simple, when using the python version of do...while you have to invert the condition!

I'm sure your algorithm is wrong. The partition function can break when they find a candidate, but must also quit when the indexes cross. — quamrana
– quamrana, Commented Aug 3, 2021 at 19:13

Алексей Р · Accepted Answer · 2021-08-03 19:27:58Z

It's need to change < and > to >= and <= in the loops:

class QuickSort:
    def sort(self, data):
        if data is None:
            raise TypeError()
        n = len(data)
        if n < 2:
            return data
        self._sort(data, 0, len(data) - 1)

    def _sort(self, A, lo, hi):
        if lo >= 0 and hi >= 0:
            if lo < hi:
                p = self._partition(A, lo, hi)
                self._sort(A, lo, p)
                self._sort(A, p + 1, hi)

    def _partition(self, A, lo, hi):
        pivot = A[(hi + lo) // 2]
        i = lo - 1
        j = hi + 1
        while True:
            while True:
                i += 1
                if A[i] >= pivot:  # >= instead of <
                    break
            while True:
                j -= 1
                if A[j] <= pivot:  # <= instead of >
                    break
            if i >= j:
                return j
            A[i], A[j] = A[j], A[i]


lst = [9, 8, 7, 6, 5, 4, 1, 2]
QuickSort().sort(lst)
print(lst) # [1, 2, 4, 5, 6, 7, 8, 9]

Collectives™ on Stack Overflow

Implementing quick sort in Python - list index/infinite loop bugs

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related