5

十分に小さいテストケース (N = 20) の正しい論理出力を確認したため、これについてはかなり混乱しています。N = 10,000 の数字を実行しようとすると、プログラムがハングアップし、その理由がわかりません... アルゴリズムをできるだけ簡単に実装しました。

sorted(data)また、私の N = 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

だから私はなぜこれが起こっているのかについてかなり迷っています。助けてくれてありがとう。

4

3 に答える 3

5

次の行にタイプミスがあるようです。

qsort(arr, 0, newPivotIndex)

こうあるべきだと思います。

qsort(arr, left, newPivotIndex)

それ以外の場合、関数は一部の入力データセットに対してのみ何らかの形で機能します。そのため、アルゴリズムがスタックします。

于 2012-07-28T07:13:46.063 に答える
2

注:アルゴリズムをチェックしていないので、問題がある可能性があります/pythonは何らかの理由でそれを好まないかもしれませんが:クイックソートは、N^2からN log(N)へのソート時間をほぼ改善しますが、おそらくそれほど悪いことではありません入力データに応じて N^2 として。最適なデータでは、N=20 と比較して N=10,000 は、40,000/26 = 1538 倍遅くなります。もしかしてただの加工？

最悪の場合のデータでは、100,000,000 / 400 = 25,000 倍遅くなります。あなたのデータは何ですか？

于 2012-07-28T06:54:51.407 に答える
2

Python は深い再帰関数のためにハングすることが多く、現在のセッションを終了するだけで (IDLE で試している場合)、何も出力せずに新しいセッションを開始することがあります。これを試してください: import sys; sys.setrecursionlimit(2**30)、常にではありませんが、これが役立つ場合があります。

于 2012-07-28T06:58:05.127 に答える