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: 終了

コード

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

時間計算量

最良のケース : 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 : 終了

コード

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

時間計算量

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

挿入ソート

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

アルゴリズム

ステップ 1: 開始
ステップ 2: i = 1
ステップ 3: if i <; len(arr)、ステップ 4 に進みます。それ以外の場合はステップ 12 に進みます
ステップ 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] = key
ステップ１１：ｉを１だけインクリメントする。ステップ 3 に進みます
ステップ 12: 終了

コード

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

時間計算量

最良のケース : O(n)
平均的なケース: 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: return merge(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: 終了

コード

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)

時間計算量

最良のケース: O(n log n)
平均ケース: 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 サイトの他の関連記事を参照してください。