ありそうもない マージソート , クイックソートは 分割統治アルゴリズム 。要素をピボットとして選択し、選択したピボットを中心に指定された配列を分割します。

QuickSort には、さまざまな方法でピボットを選択するさまざまなバージョンが存在します。

1. 常に最初の要素をピボットとして選択します
2. 常に最後の要素をピボットとして選択します
3. ランダムな要素をピボットとして選択します
4. 中央値をピボットとして選択します

ここでは、最後の要素をピボットとして選択します。 QuickSort の主要なプロセスは、partition() です。パーティションのターゲットは、配列と配列の要素 'x' をピボットとして指定し、並べ替えられた配列内の正しい位置に x を配置し、すべての小さい要素 (x より小さい) を x の前に配置し、すべての大きい要素 (x より大きい) を配置します。 x より）x 以降。これらすべては線形時間内に実行される必要があります。

パイソン 再帰的クイックソート 関数

// low -->開始インデックス, // high --> 終了インデックス QuickSort(arr[], low, high) { // 開始インデックスが終了インデックスより小さくなるまで if (low // pi はパーティション化インデックス、 // arr[p] は現在適切な場所に pi = Partition(arr, low, high); // pi の前 easySort(arr, low, pi - 1) // pi の後 easySort(arr, pi + 1, high);   
Python3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Python program for implementation of Quicksort Sort>   # This implementation utilizes pivot as the last element in the nums list>   # It has a pointer to keep track of the elements smaller than the pivot>   # At the very end of partition() function, the pointer is swapped with the pivot>   # to come up with a 'sorted' nums relative to the pivot>   # Function to find the partition position>   def>   partition(array, low, high):>   >  # choose the rightmost element as pivot>   >  pivot>  =>   array[high]>   >  # pointer for greater element>   >  i>  =>   low>  ->   1>   >  # traverse through all elements>   >  # compare each element with pivot>   >  for>   j>  in>   range>  (low, high):>   >  if>   array[j]  <>  =>   pivot:>   >  # If element smaller than pivot is found>   >  # swap it with the greater element pointed by i>   >  i>  =>   i>  +>   1>   >  # Swapping element at i with element at j>   >  (array[i], array[j])>  =>   (array[j], array[i])>   >  # Swap the pivot element with the greater element specified by i>   >  (array[i>  +>   1>  ], array[high])>  =>   (array[high], array[i>  +>   1>  ])>   >  # Return the position from where partition is done>   >  return>   i>  +>   1>   # function to perform quicksort>   def>   quickSort(array, low, high):>   >  if>   low   # Find pivot element such that  # element smaller than pivot are on the left  # element greater than pivot are on the right  pi = partition(array, low, high)  # Recursive call on the left of pivot  quickSort(array, low, pi - 1)  # Recursive call on the right of pivot  quickSort(array, pi + 1, high) data = [1, 7, 4, 1, 10, 9, -2] print('Unsorted Array') print(data) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)>  
  
  
  
  
 
     
 
     
 
   
 
  出力   
 
  
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
    時間計算量:     最悪の場合の時間計算量は O(N   2   )、平均ケース時間計算量は O(N log N) です。   
    補助スペース:     ○(1)  
  
    Python クイックソートを使用して         リストの内包表記       
  
 リスト内包表記を使用したクイックソートは、要素の配列をソートするための再帰的アルゴリズムです。これは、ピボット要素を選択し、ピボットを中心に配列を分割することによって機能します。つまり、ピボットよりも小さいすべての要素は左側に移動し、ピボットよりも大きいすべての要素は右側に移動します。次に、配列全体がソートされるまで、同じプロセスを左と右の部分配列に再帰的に適用します。  
  
    アルゴリズム：     
  
 1.入力配列の長さが 0 または 1 の場合、すでにソートされている配列を返します。   
 2.配列の最初の要素をピボット要素として選択します。   
 3.左右に 2 つの空のリストを作成します。   
 4.ピボットを除く配列内の各要素について:   
 ａ．要素がピボットより小さい場合は、左側のリストに追加します。   
 b.要素がピボット以上の場合は、それを右側のリストに追加します。   
 5.左右のリストでクイックソートを再帰的に呼び出します。   
 6.ソートされた左側のリスト、ピボット要素、およびソートされた右側のリストを連結します。   
 7.連結されたリストを返します。  
  
Python3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Approach 2: Quicksort using list comprehension>   def>   quicksort(arr):>   >  if>   len>  (arr)  <>  =>   1>  :>   >  return>   arr>   >  else>  :>   >  pivot>  =>   arr[>  0>  ]>   >  left>  =>   [x>  for>   x>  in>   arr[>  1>  :]>  if>   x   right = [x for x in arr[1:] if x>= ピボット] return クイックソート(左) + [ピボット] + クイックソート(右) # 使用例 arr = [1, 7, 4, 1, 10, 9, -2]sorted_arr = Quicksort(arr) print('Sorted Array昇順:') print(sorted_arr)>>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  出力   
 
  
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
 時間計算量は O(n log n)  
  
 アルゴリズムの空間計算量は O(n) です