13

宿題の QuickSort アルゴリズムを自分で選んだ言語で実装する必要があり、Python を選びました。

講義中、QuickSort はインプレースで動作するため、メモリ効率が高いとのことでした。つまり、再帰のための入力配列の部分の追加コピーはありません。

これを念頭に置いて、Python で QuickSort アルゴリズムを実装しようとしましたが、すぐに、洗練されたコードを記述するには、再帰中に配列の一部を関数自体に渡す必要があることに気付きました。Python はこれを行うたびに新しいリストを作成するので、Python3 を使用してみました (nonlocal キーワードがサポートされているため)。以下は私のコメント付きのコードです。

def quicksort2(array):
# Create a local copy of array.
arr = array

    def sort(start, end):
        # Base case condition
        if not start < end:
            return

        # Make it known to the inner function that we will work on arr
        # from the outer definition
        nonlocal arr

        i = start + 1
        j = start + 1

        # Choosing the pivot as the first element of the working part
        # part of arr
        pivot = arr[start]

        # Start partitioning
        while j <= end:
            if arr[j] < pivot:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                i += 1
            j += 1
        temp = arr[start]
        arr[start] = arr[i - 1]
        arr[i - 1] = temp
        # End partitioning

        # Finally recurse on both partitions
        sort(start + 0, i - 2)
        sort(i, end)
    sort(0, len(array) - 1)

今、私は仕事をうまくやったのか、それとも何かが足りないのか分かりません. 私は QuickSort のより Pythonic バージョンを作成しましたが、入力配列の一部を返し続け、それらを連結するため、その場で機能しません。

私の質問は、これはPythonでそれを行う方法ですか? Google と SO の両方を検索しましたが、QuickSort の真のインプレース実装が見つからなかったので、質問するのが最善だと思いました。

4

7 に答える 7

17

確かに最善の方法ではありません。さらに、この有名なアルゴリズムには数十の完璧な実装があります..これは私のもので、非常に理解しやすいです

def sub_partition(array, start, end, idx_pivot):

    'returns the position where the pivot winds up'

    if not (start <= idx_pivot <= end):
        raise ValueError('idx pivot must be between start and end')

    array[start], array[idx_pivot] = array[idx_pivot], array[start]
    pivot = array[start]
    i = start + 1
    j = start + 1

    while j <= end:
        if array[j] <= pivot:
            array[j], array[i] = array[i], array[j]
            i += 1
        j += 1

    array[start], array[i - 1] = array[i - 1], array[start]
    return i - 1

def quicksort(array, start=0, end=None):

    if end is None:
        end = len(array) - 1

    if end - start < 1:
        return

    idx_pivot = random.randint(start, end)
    i = sub_partition(array, start, end, idx_pivot)
    #print array, i, idx_pivot
    quicksort(array, start, i - 1)
    quicksort(array, i + 1, end)

最初に、パーティション サブルーチンの別の関数を作成します。配列、関心のある開始点と終了点、およびピボットのインデックスを取ります。この機能は明確でなければなりません

次に、クイックソートは、配列全体に対してパーティション サブルーチンを初めて呼び出します。次に recursevely 自体を呼び出して、ピボットまでのすべてとその後のすべてをソートします。

何かわからないことがあれば尋ねる

于 2013-07-21T14:50:14.980 に答える
2

最近、Python の学習を開始しました。以下は、Python を使用してクイックソートを実装する試みです。お役に立てば幸いです。フィードバックを歓迎します:) 

#!/usr/bin/python

Array = [ 3,7,2,8,1,6,8,9,6,9]

def partition(a, left, right):

    pivot = left + (right - left)/2
    a[left],a[pivot] = a[pivot], a[left] # swap
    pivot = left
    left += 1

    while right >= left :
        while left <= right and a[left] <= a[pivot] :
            left += 1
        while left <= right and a[right] > a[pivot] :
            right -= 1

        if left <= right:
            a[left] , a[right] = a[right], a[left] # swap
            left += 1
            right -= 1
        else:
            break

    a[pivot], a[right] = a[right] , a[pivot]

    return right


def quicksort(array , left,right):
    if left >= right:
        return  
    if right - left == 1:
        if array[right] < array[left]:
            array[right], array[left] = array[left] , array[right]
            return           

    pivot = partition(array, left, right)

    quicksort(array, left, pivot -1)
    quicksort(array, pivot+1,right)         

def main():
    quicksort(Array, 0 , len(Array) -1)   
    print Array 

main()
于 2014-04-04T10:03:39.160 に答える
0 
def quicksort(arr):
    lesser = []
    equal = []
    greater = []
    if len(arr)>1:
        pivot = arr[len(arr)-1]
        start = 0
        while start<len(arr):
            if arr[start] > pivot:
                greater.append(arr.pop(start)) 
            elif arr[start] < pivot:
                lesser.append(arr.pop(start))
            else:
                start = start + 1

        return (quicksort(lesser) + arr + quicksort(greater))

    else:
        return (arr)

print(quicksort([2,333,-22,0,54, 22, 37, 0.3, -2, 22]))
于 2018-10-31T07:17:40.740 に答える