Python中的QuickSort - 程序掛起以獲取更大的輸入大小？

對此很困惑，因爲我已經驗證了足夠小的測試用例正確的邏輯輸出（N = 20）。我嘗試做N = 10,000個數字，程序只是掛起，我不明白爲什麼......我已經儘可能簡單地實現了算法。Python中的QuickSort - 程序掛起以獲取更大的輸入大小？

此外，呼籲我的ňsorted(data) = 10K名單似乎幾乎立即工作。所以我相信我的算法會陷入某個地方。

下面是代碼：

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

所以我很迷失，爲什麼這可能會發生。謝謝你的幫助。

來源

2012-07-28 JDS

代碼多久才進行排序10K的數據？我實現一個更簡單的qsort和'sys.setrecursionlimit（2 ** 30）'，大約需要20〜30秒，以進行排序'[2，3，5] * 10000'，一個30k的數據。 – xiaowl 2012-07-28 07:28:49

似乎是在下面的行一個錯字：

qsort(arr, 0, newPivotIndex)

我想應該是這樣的。

qsort(arr, left, newPivotIndex)

否則，該功能將以某種方式只對某些輸入數據集有效。這就是算法卡住的原因。

來源

2012-07-28 07:13:46

你是我最喜歡的人。感謝一堆，這解決了它。 – JDS 2012-07-28 17:57:38

注意：我沒有檢查你的算法，所以可能會有問題/ python可能因爲某些原因不喜歡它，但是：快速排序將大約將排序時間從N^2提高到N log（N），但可能與N^2一樣差，具體取決於輸入數據。有了最佳數據，與N = 20相比，N = 10,000，將會是40,000/26 = 1538倍的因數。也許它只是處理？

隨着最壞的情況下數據將是億/ 400 = 25000倍慢。你的數據是什麼？

來源

2012-07-28 06:54:51 AJP

只有一次在一個藍色的月亮會我期待N^2使用隨機擺動運行時間從複雜快速排序。數據只是未排序順序的整數1至10000的通用列表。 – JDS 2012-07-28 07:11:43

只需要詢問您是否不提供rnd數據。 – AJP 2012-07-28 19:44:07

的Python常掛深遞歸函數，有時它只是終止當前的會話（如果您是在戶外嘗試它在IDLE），並沒有給予任何輸出開始一個新的會話。試試這個：import sys; sys.setrecursionlimit(2**30)，這可能會有所幫助，但並不總是如此。

來源

2012-07-28 06:58:05 SexyBeast

謝謝你，會試試這個。 – JDS 2012-07-28 07:11:56

Python中的QuickSort - 程序掛起以獲取更大的輸入大小？

回答

相關問題