Python の並べ替えアルゴリズム

並べ替えとは何ですか?

並べ替えとは、データ項目間の線形関係に基づいて、データを特定の順序 (通常は昇順または降順) に配置するプロセスを指します。

なぜ並べ替えが必要なのでしょうか?

並べ替えは、効率的なデータの取得を可能にし、データ分析を簡素化し、全体的なデータ管理を強化するため、構造化データを扱う場合に非常に重要です。

ソートアルゴリズム

この投稿では、バブル ソート、選択ソート、挿入ソート、マージ ソート、クイック ソートの並べ替えアルゴリズムについて説明します。

バブルソート

バブルソートは配列を繰り返しステップ実行し、隣接する要素を比較し、順序が間違っている場合は入れ替えます。このプロセスは、配列がソートされ、より大きな要素が最後まで「バブリング」するまで続きます。

アルゴリズム

ステップ 1: 始める
ステップ 2: i = 0
ステップ 3: if i ステップ 4: j = 0
ステップ 5: j ステップ6: 配列[j] > の場合array[j + 1]、ステップ 7 に進みます。それ以外の場合はステップ 8 に進みます
ステップ 7: array[j] と array[j + 1] を交換します
ステップ 8: j をインクリメントします。ステップ 5 に進みます
ステップ 9: i をインクリメントします。ステップ 3 に進みます
ステップ 10: 終了

コード

時間計算量

ベストケース: O(n)
平均的なケース: O(n^2)
最悪の場合: O(n^2)

選択範囲の並べ替え

選択ソートは、配列のソートされていない部分の最小値を見つけて、その部分の先頭に配置します。

アルゴリズム

ステップ 1: 始める
ステップ 2: i = 0
ステップ 3: if i ステップ 4: 最小値 = i; j = i + 1
ステップ 5: j ステップ 6 : 配列[最小値] > の場合array[j]、ステップ 7 に進みます。それ以外の場合はステップ 8 に進みます
ステップ 7 : minimum_value = j
ステップ 8: j をインクリメントします。ステップ 5 に進みます
ステップ 9 : array[minimum_value] と array[i] を交換します
ステップ 10: i をインクリメントします。ステップ 3 に進みます
ステップ 11: 終了

コード

時間計算量

ベストケース: O(n^2)
平均的なケース: O(n^2)
最悪の場合: O(n^2)

挿入ソート

挿入ソートは、未ソート部分から各要素を取得し、それをソート部分の正しい位置に挿入することにより、一度に 1 要素ずつソートされた配列を構築します。

ステップ 2: i = 1
ステップ 3: if i ステップ 4: key = arr[i]
ステップ 5: j = i - 1
ステップ 6: j >= 0 かつ arr[j] > の場合キーを押してステップ 7 に進みます。それ以外の場合はステップ 10 に進みます
ステップ 7: arr[j + 1] = arr[j]
ステップ 8: j を 1 だけデクリメントします
ステップ 9: ステップ 6 に進みます
ステップ 10: arr[j + 1] = キー
ステップ１１：ｉを１だけインクリメントする。ステップ 3 に進みます
ステップ 12: 終了

リーリー

平均的なケース: O(n^2)
最悪の場合: O(n^2)

マージソートアルゴリズム
ステップ 1: 始める
ステップ 2: length(array) ステップ 3:mid_point = length(array) // 2
ステップ 4: left_half = array[:mid_point]
ステップ 5: right_half = array[mid_point:]
ステップ 6:sorted_left = merge_sort(left_half)
ステップ 7:sorted_right = merge_sort(right_half)
ステップ 8: マージを返す(sorted_left、sorted_right)
ステップ9: 終了

マージ関数
ステップ 1: 始める
ステップ 2:sorted_merge = []
ステップ 3: l = 0、r = 0
ステップ 4: l ステップ 5: left[l] ステップ6: left[l]をsorted_mergeに追加します。 lを1ずつ増分します
ステップ 7: right[r] をsorted_mergeに追加します。 rを1増やす
ステップ 8: ステップ 4 に進みます
ステップ9: l ステップ 10: left[l] をsorted_merge に追加します。 lを1ずつ増分します
ステップ 11: ステップ 9 に進みます
ステップ 12: r ステップ 13: right[r] をsorted_merge に追加します。 rを1増やす
ステップ 14: ステップ 12 に進みます
ステップ 15:sorted_merge を返す
ステップ 16: 終了

リーリー

平均的なケース: O(n log n)
最悪の場合: O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

def partition(arr, low, high): pivot = arr[high] left = low right = high - 1 while left <= right: if arr[left] > pivot and arr[right] < pivot: arr[left], arr[right] = arr[right], arr[left] if arr[left] <= pivot: left += 1 if arr[right] >= pivot: right -= 1 arr[left], arr[high] = arr[high], arr[left] return left def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high) # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) quicksort(arr, 0, len(arr) - 1) print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

以上がPython の並べ替えアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。