クイックソートアルゴリズム（Python）を改善するには

Question

クイックソートアルゴリズムを読んだ後、コードを調べる前に独自の実装を作成することにしました。以下のコードは、私が思いついたものです。私のコードを他の実装と比較すると、ソートされた配列をクイックソート関数から返すのではなく、他の実装ではリストの変更可能性を利用する傾向があり、配列をソートする配列関数呼び出しを参照する必要はありません。私は自分のコードと私が使っている本のコードとの空間時間の比較について興味があります。私は、時間に関しては、アルゴリズムがむしろ同様に機能していると仮定しています。実行している連結演算に悪影響が及ぶ可能性はありますか？スペースに関しては、入力配列を直接変更しないので、私は、明らかに非効率な新しい配列を作成/返すと仮定しています。マージソートに対するクイックソートの主な利点は保存されたスペースです。全体的に私はアルゴリズムの効率を向上させるためのいくつかの追加の洞察と方法を探しています。

マイコード：

from random import randint 

def quick(arr): 
    if len(arr) == 1: 
    return arr 
    else: 

    pivot = arr[0] 
    R = len(arr)-1 
    L = 1 

    while L <= len(arr)-1 and R >= 1: 
     if R == L: 
      if arr[0] > arr[R]: 
       arr[0], arr[R] = arr[R], arr[0] 
      break 
     if arr[R] >= pivot: 
      R = R - 1 
      continue 
     if arr[L] <= pivot: 
      L = L + 1 
      continue 
     arr[L], arr[R] = arr[R], arr[L] 
    return quick(arr[:R]) + quick(arr[R:]) 

print quick([randint(0,1000) for i in range(1000)]) 

私が使用している書籍、問題ブラッド・ミラーとDavid RanumではPythonの使用アルゴリズムとデータ構造で解く、このクイックソートのコードを提供します。

def quickSort(alist): 
    quickSortHelper(alist,0,len(alist)-1) 

def quickSortHelper(alist,first,last): 
    if first<last: 

    splitpoint = partition(alist,first,last) 

    quickSortHelper(alist,first,splitpoint-1) 
    quickSortHelper(alist,splitpoint+1,last) 


def partition(alist,first,last): 
    pivotvalue = alist[first] 

    leftmark = first+1 
    rightmark = last 

done = False 
while not done: 

    while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 
    leftmark = leftmark + 1 

    while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 
    rightmark = rightmark -1 

    if rightmark < leftmark: 
     done = True 
    else: 
     temp = alist[leftmark] 
     alist[leftmark] = alist[rightmark] 
     alist[rightmark] = temp 

temp = alist[first] 
alist[first] = alist[rightmark] 
alist[rightmark] = temp 

return rightmark 

# alist = [54,26,93,17,77,31,44,55,20] 
# quickSort(alist) 
# print(alist) 

Answer 1

この素晴らしいコードです。

（1つのアレイのみを使用して）クイックソートのバージョンと比較すると、コピー/連結のために少し遅くなることがあります。

クイックソートのパフォーマンスは、ピボットの選択に大きく依存しています。最初の要素を選択することによって、コードが二次的に実行される場合があります。たとえば、すでにソートされた配列をソートする場合です。 最も知られているの最適化は、以下のとおりです。（あなたはほぼ確実に、これらの最悪のケースを避けるため）Tukeyのnintherを適用することによって、例えば、より良いピボットを選ぶ

• 。
• サブアレイが十分に小さいときに挿入ソートを実行します（たとえば、<）。エルス

、3ウェイクイックソート（Javaでプリミティブの配列をソートするために使用される）ベントレー・マッキロイのshemeまたはデュアルピボットクイックソートを使用してのように高速に実行クイックソートのいくつかの変異体は、あります。挿入のスピードアップはそれらにも適用されます。