quick sort recursion error

Question

My thoughts: i'm trying to implement quick sort with python. i set the first element as pivot. if the element of left mark is larger than pivot then i start moving the right mark to find an element smaller than pivot and then swap. if right mark is smaller than left mark, swap pivot with the element of right mark. then separate the list with pivot. and repeat the step

Question: my code can separate the list into two lists as i imagined. but when it returns it somehow copy the elements several times and made it wrong. i'm not familiar with recursion and can't find the problem.

def quick_sort(lst):
    front = []
    rear = []
    temp = 0
    pivot = lst[0]
    i = 1                 #leftmark
    j = len(lst)-1        #rightmark
    if len(lst) == 1:
        return lst
    while i<=j:
        if lst[i]<pivot:
            i+=1
        else:
            if lst[j]>pivot:
                j-=1
            elif lst[j] == pivot:
                break
            else:
                temp = lst[i]
                lst[i] = lst[j]
                lst[j] = temp

    '''if j<i  (rightmark < leftmark) swap pivot with position j'''
    temp = pivot
    pivot = lst[j]
    lst[j] = temp
    lst[0] = pivot
    front = lst[0:j+1]
    rear = lst[i:len(lst)+1]
    return quick_sort(front) + [pivot] + quick_sort(rear)

You should be changing your i and j values accordingly in the recursive list.In this the i and j values are always 1 and len(lst-1) respectively — DineshKumar, Aug 10 '16 at 03:55

score 0 · Accepted Answer · answered Aug 10 '16 at 03:55

You are slicing the list wrong. You should replace lst[0:j+1] to lst[ : j ] and lst[i:len(lst)+1] to lst[ j + 1 : ], since the pivot is at position jand you should ignore it (here, the emptiness before : represent from the start and after : represent till the end). Last but not least, consider using tuples to swap instead of temp var, example:

temp = a
a = b
b = temp

can be replaced by the one liner

a, b = b, a

here is my final working code:

def quick_sort(lst):
    if lst:
        pivot = lst[0]
        i = 1                 #leftmark
        j = len(lst)-1        #rightmark
        if len(lst) == 1:
            return lst
        while i <= j:
            if lst[i] < pivot:
                i += 1
            elif lst[j]>pivot:
                    j-=1
            elif lst[j] == pivot:
                break
            else:
                lst[i], lst[j] = lst[j], lst[i]
        '''if j<i  (rightmark < leftmark) swap pivot with position j'''
        lst[0], lst[j] = lst[j], lst[0]
        front = lst[ : j ]
        rear = lst[ j+1 : ]
        return quick_sort(front) + [ pivot ] + quick_sort(rear)
    return []

>>> quick_sort([1,3,4,2,6,9,0])
[0, 1, 2, 3, 4, 6, 9]

quick sort recursion error

1 Answers1