Cần giúp đỡ về thuật toán QuickSort trong Python

ngnduchai · July 23, 2015, 3:56am

Em mới học Python và hơi ngu phần thuật toán ạ, vì e tự học và vì e học trường không chuyên bên lập trình Hầu hết tự học
Em hiểu thuật toán quicksort như thế này, và trình bày nó trong python, phần tử chốt e chọn là phần tử ở giữa.
Sao code không chạy được và báo lỗi: “RuntimeError: maximum recursion depth exceeded while calling a Python object”. Em xin cảm ơn!

def quicksort(data,left,right):
    pivot=data[int((len(data)-1)/2)]
    i=left
    j=right
    while i<=j:
        while data[i]<pivot:
            i+=1
        while data[j]>pivot:
            j-=1
        if i<=j:
            temp=data[i]
            data[i]=data[j]
            data[j]=temp
            i+=1
            j-=1
    if left<j:
        quicksort(data,left,j)
    if i<right:
        quicksort(data,i,right)
    return data

danhsach = [4, 6, 3, 7, 2]
ketqua = quicksort(danhsach,0,4)
print(ketqua)

drgnz · July 23, 2015, 4:12am

Làm vậy để chặn lỗi tràn stack thôi ‘3’
Bạn có thể dùng sys.setrecursionlimit(number) để tăng thêm “chiều sâu” của đệ quy

hailuut · July 23, 2015, 4:19am

Set lên bao nhiêu cũng vậy thôi, vì thuật toán này không có điều kiện dừng, nên nó sẽ chạy mãi.

programmerit · July 23, 2015, 4:23am

Mình có viết một bài trên blog cá nhân về thuật toán Quicksort cài đặt bằng Python và C. Bạn tham khảo ở đây nhé: http://chingovan.blogspot.com/2015/07/algorithm-thuat-toan-sap-xep-nhanh.html
Về code của bạn thì mình có ý như thế này:

Chỗ if i <= j theo mình là bỏ dấu bằng đi vì không cần thiết.
Lúc phần chia dãy bạn phải cẩn thận hơn, cân nhắt trường hợp chọn chốt đúng vào phần tử lớn nhất hoặc nhỏ nhất.

tntxtnt · July 23, 2015, 4:25am

dừng đc mà, có điều chọn pivot sai thôi. Chọn pivot như trên lúc nào cũng là phần tử nằm giữa của mảng ban đầu, trong cái ví dụ kia thì pivot luôn luôn là 3, nên nó cứ chạy mãi cái quicksort nhánh bên phải.
phải là data[(left+right)/2], hay là phần tử nằm giữa left và right thì mới dừng được. Hoặc chọn pivot là phần tử đầu tiên cũng được: pivot = data[left]

ngnduchai · July 23, 2015, 1:37pm

Cảm ơn mọi người, chỉ cần sửa vị trí chốt lại là có thể chạy được