5
Khá bối rối về điều này vì tôi đã xác minh đầu ra hợp lý chính xác cho các testcases đủ nhỏ (N = 20). Tôi cố gắng làm N = 10.000 số và chương trình chỉ bị treo và tôi không hiểu tại sao ... Tôi đã triển khai thuật toán đơn giản nhất có thể.QuickSort bằng Python - chương trình bị treo cho kích thước đầu vào lớn hơn?
Ngoài ra, gọi sorted(data) trên danh sách N = 10k của tôi dường như hoạt động gần như ngay lập tức. Vì vậy, tôi tin rằng thuật toán của tôi chỉ bị kẹt ở đâu đó.
Đây là mã:
def QuickSort(array):
qsort(array, 0, len(array))
def qsort(arr, left, right):
if ((right - left) < 2):
return
pivotIndex = choosePivot0(arr, left, right)
newPivotIndex = partition(arr, pivotIndex, left, right)
qsort(arr, 0, newPivotIndex)
qsort(arr, newPivotIndex + 1, right)
def partition(arr, pivotIndex, left, right):
swap(arr, pivotIndex, left)
pivot = arr[left]
i = left + 1
for j in range(left+1, right):
if (arr[j] < pivot):
swap(arr, i, j)
i = i + 1
swap(arr, left, i-1) #put pivot back where it belongs
#cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons
return (i-1) #give back where the pivot resides
def swap(array, i, j):
temp = array[i]
array[i] = array[j]
array[j] = temp
def choosePivot0(array, left, right):
return randint(left, right-1) #random
Vì vậy, tôi khá mất là tại sao điều này có thể xảy ra. Cảm ơn vì bất kì sự giúp đỡ.
Mã của bạn mất bao lâu để sắp xếp dữ liệu 10k? Tôi đã thực hiện một qsort đơn giản và 'sys.setrecursionlimit (2 ** 30)', mất khoảng 20 ~ 30 giây để sắp xếp '[2, 3, 5] * 10000', một dữ liệu 30k. – xiaowl