並べ替えとは、データ項目間の線形関係に基づいて、データを特定の順序 (通常は昇順または降順) に配置するプロセスを指します。
並べ替えは、効率的なデータの取得を可能にし、データ分析を簡素化し、全体的なデータ管理を強化するため、構造化データを扱う場合に非常に重要です。
この投稿では、バブル ソート、選択ソート、挿入ソート、マージ ソート、およびクイック ソートの並べ替えアルゴリズムについて説明します。
バブル ソートは配列を繰り返しステップ実行し、隣接する要素を比較し、順序が間違っている場合は入れ替えます。このプロセスは、配列がソートされ、より大きな要素が最後まで「バブリング」するまで続きます。
ステップ 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 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.
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
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)
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
以上がPython の並べ替えアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
