0

単純なクイックソートの実装であるべきものがありますが、再帰の深さを超えたエラーが返され、30 未満の要素のリストでテストしています。さらに、私の実装は数日前に 10,000 のリストに取り組んでいました。私が変更したのは、それをクラスからグローバル関数に移動したことだけでした。誰がこれを引き起こしているのか分かりますか? 

def quickSort(m, left, right):
    if len(m[left:right]) <= 1:
        return m
    pivot = m[left]
    i = left + 1
    j = left + 1
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    m = quickSort(m, left, i)
    m = quickSort(m, i, right)
    return m
4

1 に答える 1

2

再帰呼び出しの1つが例外を引き起こしています(ご想像のとおり:-)。また、リストを適切にソートするため、リストを返す必要がないことに注意してください

def quickSort(m, left, right):
    if right - left  <= 1:
        return

    pivot = m[left]
    i = left + 1 
    j = left + 1 
    for j in range(j, right):
        if m[j] <= pivot:
            m[j], m[i] = m[i], m[j]
            i += 1
    m[left], m[i-1] = m[i-1], m[left]
    quickSort(m, left, i-1)
    quickSort(m, i, right)
于 2012-11-14T19:31:22.727 に答える