30/09/2018, 17:39
Cần giúp đỡ về thuật toán QuickSort trong Python
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)
Bài liên quan
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
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.
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:
if i <= jtheo mình là bỏ dấu bằng đi vì không cần thiết.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ữaleftvàrightthì mới dừng được. Hoặc chọn pivot là phần tử đầu tiên cũng được:pivot = data[left]Cảm ơn mọi người, chỉ cần sửa vị trí chốt lại là có thể chạy được