0

Python 3 で整数の ctypes 配列にいくつかの並べ替えメソッドを実装しようとしていますが、Quicksort メソッドを理解できないようです。私のコードの大部分は正しいと思いますが、ばかげたステートメントが欠けているだけです。現在、これが返す配列を印刷しようとしたときに得られるのは、「NoneType」オブジェクトだけです。

本当にありがとう。

#Quicksort Algorithm
def quicksort(list):
    n = len(list)
    return recquick(list, 0, n-1)

#Recursive Quicksort Function
def recquick(list, first, last):
    #Base Case
    if first >= last:
        return
    else:
        #Save pivot value
        pivot = list[first]

        pos = partseq(list, first, last)

        #Repeat the process on the two subsequences
        recquick(list, first, pos-1)
        recquick(list, pos+1, last)

#Partitions subsequence using first key as pivot
def partseq(list, first, last):
    #Save pivot value
    pivot = list[first]

    #Find pivot position and move elements around the pivot
    left = first + 1
    right = last
    while left <= right:
        #Find the first key larger than the pivot
        while left < right and list[left] < pivot:
            left += 1

        #find the last key in the sequence that is smaller than the pivot
        while right >= left and list[right] >= pivot:
            right -= 1


        #Swap the two keys
        if left < right:
            tmp = list[left]
            list[left] = list[right]
            list[right] = tmp

        #Put the pivot in the proper position
        if right != first:
            list[first] = list[right]
            list[right] = pivot

        #Return index position of the pivot value
        return right
4

1 に答える 1

1

外側の while ループが適切ではありませんpartseq。右とピボットの交換は、while ループの外で 1 回だけ行う必要があります。return ステートメントも while の外にある必要があります

また、このリンクに基づいて、アルゴリズムに小さな調整を加えました

  • leftから始まるfirst
  • 最初の内側の while ループは終了まで実行list[left] <= pivotされ、2 番目の内側の while ループは終了まで実行されます。list[right] > pivot
#Quicksort Algorithm
def quicksort(list):
    n = len(list)
    return recquick(list, 0, n-1)

#Recursive Quicksort Function
def recquick(list, first, last):
    #Base Case
    if first >= last:
        return
    else:
        #Save pivot value
        pivot = list[first]

        pos = partseq(list, first, last)

        #Repeat the process on the two subsequences
        recquick(list, first, pos-1)
        recquick(list, pos+1, last)

#Partitions subsequence using first key as pivot
def partseq(list, first, last):
    #Find pivot position and move elements around the pivot
    pivot = list[first]

    left = first 
    right = last
    while left<right: 
        #Find the first key larger than the pivot

        while left < right and list[left] <= pivot:
            left += 1

        #find the last key in the sequence that is smaller than the pivot
        while right >= left and list[right] > pivot:
            right -= 1

        #Swap the two keys
        if left < right:
            tmp = list[left]
            list[left] = list[right]
            list[right] = tmp


    #Put the pivot in the proper position
    #right to left
    if right != first:
        list[first] = list[right]
        list[right] = pivot

    #Return index position of the pivot value
    return right

結果

>>> import try1
>>> a=[1,2,3,4,5,6,]
>>> try1.quicksort(a)
>>> a
[1, 2, 3, 4, 5, 6]
>>> a=[6,5,4,3,2,1,]
>>> try1.quicksort(a)
>>> a
[1, 2, 3, 4, 5, 6]
>>> a=[1]
>>> try1.quicksort(a)
>>> a
[1]
>>> a=[]
>>> try1.quicksort(a)
>>> a
[]
>>> a=[43,76,9,10,1,15,62,]
>>> try1.quicksort(a)
>>> a
[1, 9, 10, 15, 43, 62, 76]
于 2013-03-28T09:32:37.950 に答える