PythonのQuickSort - 入力サイズが大きい場合にプログラムがハングアップしますか？

Question

私は十分に小さいテストケース（N = 20）に対して正しい論理出力を検証しているので、かなり混乱しています。私はN = 10,000の数字をやろうとしていますが、プログラムがハングアップするだけです。理由はわかりません。できるだけ簡単にアルゴリズムを実装しました。

また、私のN = 10Kリストにsorted(data)を呼び出すと、ほぼ瞬時に動作するようです。だから、私のアルゴリズムはちょうどどこかに詰まっていると確信しています。ここで

コードです：だから私はかなりこれが起こっ可能理由を失ってい

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 

。助けてくれてありがとう。

Answer 1

次の行にタイプミスがあるようです：私は、それはこのようにすべきだと思います

qsort(arr, 0, newPivotIndex) 

。

qsort(arr, left, newPivotIndex) 

それ以外の場合は、入力データセットの一部に対してのみ機能します。それが理由でアルゴリズムが止まってしまいます。

Answer 2

注：私はあなたのアルゴリズムをチェックしていないので、何かの理由でPythonがそれを好きではないかもしれませんが： クイックソートはN^2からN log（N）しかし、入力データに応じてN^2ほど悪いかもしれません。最適なデータでは、N = 20と比較してN = 10,000であり、40,000/26 = 1538倍遅い。たぶんそれはちょうど処理ですか？最悪の場合データと

それは100,000,000/400 = 25,000倍遅くなります。あなたのデータは何ですか？

Answer 3

Pythonは深い再帰関数でハングアップすることがよくあります。現在のセッションを終了するだけで（IDLEで試してみると）、何も出力せずに新鮮なセッションを開始します。これを試してみてください：import sys; sys.setrecursionlimit(2**30)、いつもそうとは限りませんが、これは役に立ちます。