CODEWITHSUNDEEP
pythoninfinite-loopquicksortindex-error
msm1089
msm1089

Reputation: 1504

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

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!

Upvotes: 0

Views: 40

Answers (1)

Алексей Р
Алексей Р

Reputation: 7627

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]

Upvotes: 1

Related Questions