3ウェイクイックソートの実装

Question

私はアルゴリズムの初心者です。私が割り当てとして書いているコードのどこにエラーがあるのか​​混乱しています。私は配列の等しい値を扱うPython 3でクイックソートアルゴリズムを実装しようとしています。ここで

はクイックソート機能（アレイ用スタンド）です：

def randomized_quick_sort(a, l, r): 
    if l >= r: 
     return 
    k = random.randint(l, r) 
    a[l], a[k] = a[k], a[l] 
    m1, m2 = partition3(a, l, r) 
    randomized_quick_sort(a, l, m1 - 1); 
    randomized_quick_sort(a, m2 + 1, r); 

そしてここでは、私のパーティション機能です：ここで

def partition3(a, l, r): 
    x, j, t = a[l], l, r 
    for i in range(l + 1, r + 1): 
     if a[i] < x: 
      j +=1 
      a[i], a[j] = a[j], a[i] 
     elif a[i] > x: 
      a[i], a[t] = a[t], a[i] 
      t -=1 
     else: 
      j +=1 
    a[l], a[j] = a[j], a[l] 
    return j, t 

Answer 1

はPythonで死んでシンプルなクイックソートの実装です。それはまだnlognですが、実行可能なパフォーマンスの最適化がたくさんあります。例えば、アレイの3回のパスではなく、1回のパスでより小さい、等しい、より大きいパーティションへの分割を行うことができます。

def qsort(arr): 
    if len(arr) <= 1: return arr 
    pivot = arr[0] 
    less = [x for x in arr if x < pivot] 
    equal = [x for x in arr if x == pivot] 
    greater = [x for x in arr if x > pivot] 
    return qsort(less) + equal + qsort(greater) 

そのパーティションは、次のようなヘルパー関数を作る、配列の1回のパスで実現するために：

def partition(arr, pivot): 
    less, equal, greater = [], [], [] 
    for val in arr: 
     if val < pivot: less.append(val) 
     if val == pivot: equal.append(val) 
     if val > pivot: greater.append(val) 
    return less, equal, greater 

def qsort(arr): 
    if len(arr) <= 1: return arr 
    pivot = arr[0] 
    less, equal, greater = partition(arr, pivot) 
    return qsort(less) + equal + qsort(greater) 

Answer 2

あなたは、パーティション機能を是正する必要があります

ここでは、実施例です。

def partition3(a, l, r): 
    x, j, t = a[l], l, r 
    i = j 

    while i <= t : 
     if a[i] < x: 
     a[j], a[i] = a[i], a[j] 
     j += 1 

     elif a[i] > x: 
     a[t], a[i] = a[i], a[t] 
     t -= 1 
     i -= 1 # remain in the same i in this case 
     i += 1 
    return j, t 

Answer 3

forループによる別の実装

def partition3(a, l, r): 
    x = a[l] 
    m1 = l 
    m2 = l 
    i = m1 
    for i in range(l + 1, r + 1): 
     if a[i] < x: 
      a[i], a[m1] = a[m1], a[i] 
      a[i], a[m2+1] = a[m2+1], a[i] 
      m1 += 1 
      m2 += 1 
     elif a[i] == x: 
      a[i], a[m2+1] = a[m2+1], a[i] 
      m2 += 1 
    return m1, m2