アプリケーションで保存したり取得したりするデータには、ほとんど順序がないことがあります。データを正しく処理したり、効率的に利用するためには、データを並べ替えなければならないことがあります。長年にわたり、コンピュータ科学者はデータを整理するために多くのソートアルゴリズムを作成してきました。
この記事では、人気のあるソートアルゴリズムを見て、その仕組みを理解し、Pythonでコーディングします。また、リスト内の項目をどれだけ速くソートできるかを比較します。
簡単のために、アルゴリズムの実装は数値のリストを昇順でソートすることになります。もちろん、あなたの必要性に応じて自由にアレンジしてください。
バブルソート
この単純なソートアルゴリズムは、リストを繰り返し処理し、2つの要素を比較し、大きな要素がリストの最後に「バブルアップ」し、小さな要素が「ボトム」に留まるまでそれらを交換します。
説明
まず、リストの最初の2つの要素を比較します。もし最初の要素が2番目の要素より大きければ、それらを入れ替えます。すでに順番が決まっている場合は、そのままにします。次に、次の要素のペアに移り、それらの値を比較し、必要に応じて入れ替えます。この処理をリストの最後の組まで続ける。
リストの最後に到達すると、すべての項目に対してこの処理を繰り返す。しかし、これは非常に非効率的です。もし、スワップが1回しか必要なかったらどうでしょう？すでにソートされているにもかかわらず、なぜn^2回繰り返すのでしょうか？
明らかに、アルゴリズムを最適化するためには、ソートが終了した時点でアルゴリズムを停止する必要があります。そうしないと、すでにソートされた配列を何度も評価し直すことになります。
ソートが終わったことをどうやって知るのでしょうか？もし項目が順番に並んでいれば、入れ替えをする必要はありません。そこで、値を入れ替えるたびにフラグを True に設定し、ソート処理を繰り返すようにしています。もし入れ替えが行われなければ、フラグは False のままとなり、アルゴリズムは停止します。
バブルソートに関するより詳細な専門的な記事を読みたい方は、こちらをご覧ください。
実装
この最適化により、PythonでBubble Sortを以下のように実装することができる。
def bubble_sort(nums):
# We set swapped to True so the loop looks runs at least once
swapped = True
while swapped:
swapped = False
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
# Swap the elements
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Set the flag to True so we'll loop again
swapped = True
# Verify it works
random_list_of_nums = [5, 2, 1, 8, 4]
bubble_sort(random_list_of_nums)
print(random_list_of_nums)
このアルゴリズムは while ループで実行され、アイテムが入れ替わらなかったときのみ終了します。このアルゴリズムが少なくとも一度は実行されることを保証するために、 swapped を True に設定します。
時間的複雑性
最悪の場合（リストが逆順の場合）、このアルゴリズムは配列のすべての項目を交換する必要があります。スワップされたフラグは反復処理ごとにTrue` にセットされます。
したがって、リストに n 個の要素がある場合、各項目ごとに n 回の反復処理を行うことになります。
選択ソート
このアルゴリズムは、リストをソート済みとソート外の2つの部分に分割する。リストのソートされていない部分の最小の要素を連続的に削除し、ソートされた部分に追加する。
説明
実際には、ソートされた要素のために新しいリストを作成する必要はなく、リストの左端をソートされたセグメントとして扱います。そして、リスト全体を検索して最小の要素を探し、それを最初の要素と交換します。
これでリストの最初の要素がソートされていることがわかったので、残りの項目の最小の要素を取得し、それを2番目の要素と交換します。これを、リストの最後の項目が調べるべき残りの要素になるまで繰り返す。
実装
def selection_sort(nums):
# This value of i corresponds to how many values were sorted
for i in range(len(nums)):
# We assume that the first item of the unsorted segment is the smallest
lowest_value_index = i
# This loop iterates over the unsorted items
for j in range(i + 1, len(nums)):
if nums[j] < nums[lowest_value_index]:
lowest_value_index = j
# Swap values of the lowest unsorted element with the first unsorted
# element
nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]
# Verify it works
random_list_of_nums = [12, 8, 3, 20, 11]
selection_sort(random_list_of_nums)
print(random_list_of_nums)
i`が大きくなると、チェックする項目が少なくなることがわかります。
時間的複雑性
選択ソートアルゴリズムの「for」ループを調べれば、簡単に時間計算量がわかります。n個の要素を持つリストに対して、外側のループはn回反復します。
内側のループは、iが1になったらn-1回、iが2になったらn-2回と、繰り返し処理を行います。
比較の回数は、(n - 1) + (n - 2) + ...'となる。+ 1となり、Selection Sortの時間計算量はO(n^2)となります。
挿入ソート
選択ソートと同様に、このアルゴリズムもリストをソート済み部分と未ソート部分に分割します。ソートされていないセグメントを繰り返し、表示されている要素をソートされたリストの正しい位置に挿入します。
説明
リストの最初の要素がソートされていると仮定する。次に、次の要素、仮に x とする、に行く。もし x が最初の要素より大きければ、そのままにします。もし x が小さければ、最初の要素の値を 2 番目の位置にコピーして、最初の要素に x をセットします。
ソートされていないセグメントの他の要素に移動するとき、ソートされたセグメント内の大きな要素を、 x より小さな要素に出会うまで、またはソートされたセグメントの最後に達するまで、リストの上に継続的に移動させ、そして x を正しい位置に配置します。
挿入ソートに関する詳細な専門記事を読みたい場合は、こちらを参照してください。
実装
def insertion_sort(nums):
# Start on the second element as we assume the first element is sorted
for i in range(1, len(nums)):
item_to_insert = nums[i]
# And keep a reference of the index of the previous element
j = i - 1
# Move all items of the sorted segment forward if they are larger than
# the item to insert
while j >= 0 and nums[j] > item_to_insert:
nums[j + 1] = nums[j]
j -= 1
# Insert the item
nums[j + 1] = item_to_insert
# Verify it works
random_list_of_nums = [9, 1, 15, 28, 6]
insertion_sort(random_list_of_nums)
print(random_list_of_nums)
時間的複雑性
最悪の場合、配列は逆順にソートされます。挿入ソート関数の外側の for ループ は常に n-1 回反復する。
最悪の場合、内側の for ループ は 1 回スワップし、次に 2 回スワップし、…と繰り返すことになる。この場合、スワップ回数は「1 + 2 + …」となります。+ (n – 3) + (n – 2) + (n – 1)` となり、挿入ソートの時間計算量は O(n^2) となります。
ヒープソート
この一般的なソートアルゴリズムは、挿入ソートや選択ソートと同様に、リストをソート済み部分と未ソート部分に分割します。ソートされていないリストのセグメントをヒープデータ構造に変換し、最大の要素を効率的に決定できるようにします。
説明
まず、リストを最大ヒープ（最大の要素をルートノードとする二分木）に変換する。そして、その項目をリストの末尾に配置します。次に、リストの最後の項目の前に新しい最大の値を配置し、値が1つ少なくなったマックスヒープを再構築します。
すべてのノードが削除されるまで、このヒープを構築するプロセスを繰り返します。
ヒープソートに関する詳細な記事を読みたい方は、こちらをご覧ください。
実装
このアルゴリズムを実装するために、ヘルパー関数 heapify を作成する。
def heapify(nums, heap_size, root_index):
# Assume the index of the largest element is the root index
largest = root_index
left_child = (2 * root_index) + 1
right_child = (2 * root_index) + 2
# If the left child of the root is a valid index, and the element is greater
# than the current largest element, then update the largest element
if left_child < heap_size and nums[left_child] > nums[largest]:
largest = left_child
# Do the same for the right child of the root
if right_child < heap_size and nums[right_child] > nums[largest]:
largest = right_child
# If the largest element is no longer the root element, swap them
if largest != root_index:
nums[root_index], nums[largest] = nums[largest], nums[root_index]
# Heapify the new root element to ensure it's the largest
heapify(nums, heap_size, largest)
def heap_sort(nums):
n = len(nums)
# Create a Max Heap from the list
# The 2nd argument of range means we stop at the element before -1 i.e.
# the first element of the list.
# The 3rd argument of range means we iterate backwards, reducing the count
# of i by 1
for i in range(n, -1, -1):
heapify(nums, n, i)
# Move the root of the max heap to the end of
for i in range(n - 1, 0, -1):
nums[i], nums[0] = nums[0], nums[i]
heapify(nums, i, 0)
# Verify it works
random_list_of_nums = [35, 12, 43, 8, 51]
heap_sort(random_list_of_nums)
print(random_list_of_nums)
時間的複雑性
まず、heapify関数の時間計算量を見てみましょう。最悪の場合、最大の要素がルート要素になることはなく、 heapify の再帰的な呼び出しが発生します。再帰的な呼び出しは非常に高く感じるかもしれませんが、私たちが扱っているのは2分木であることを思い出してください。
次に、7つの要素を持つ2分木を考えてみましょう。この2分木は高さが3です。
heap_sort` 関数は配列に対して n 回反復処理を行います。したがって、ヒープソートアルゴリズムの全体の時間計算量は O(nlog(n)) となります。
マージソート
この分割統治アルゴリズムは、リストを半分に分割し、単数要素だけになるまで2分割し続ける。
隣接する要素はソートされたペアになり、ソートされたペアは他のペアとマージされ、同様にソートされます。この処理は、ソートされていない入力リストの全要素を含むソート済みリストが得られるまで続けられます。
説明
リストを再帰的に半分に分割し、サイズ1のリストを作成する。次に、分割された各半分を結合し、その過程でソートする。
ソートは各半分の最小の要素を比較することによって行われます。各リストの最初の要素が最初に比較されます。もし前半が小さい値で始まっていれば、それをソートされたリストに追加します。次に、前半の2番目に小さい値と後半の1番目に小さい値を比較します。
半分の先頭でより小さい値を選択するたびに、どの項目を比較すべきかのインデックスを1つずつ動かしていきます。
マージソートの詳細な専用記事を読みたい方は、こちらをご覧ください。
実装
def merge(left_list, right_list):
sorted_list = []
left_list_index = right_list_index = 0
# We use the list lengths often, so its handy to make variables
left_list_length, right_list_length = len(left_list), len(right_list)
for _ in range(left_list_length + right_list_length):
if left_list_index < left_list_length and right_list_index < right_list_length:
# We check which value from the start of each list is smaller
# If the item at the beginning of the left list is smaller, add it
# to the sorted list
if left_list[left_list_index] <= right_list[right_list_index]:
sorted_list.append(left_list[left_list_index])
left_list_index += 1
# If the item at the beginning of the right list is smaller, add it
# to the sorted list
else:
sorted_list.append(right_list[right_list_index])
right_list_index += 1
# If we've reached the end of the of the left list, add the elements
# from the right list
elif left_list_index == left_list_length:
sorted_list.append(right_list[right_list_index])
right_list_index += 1
# If we've reached the end of the of the right list, add the elements
# from the left list
elif right_list_index == right_list_length:
sorted_list.append(left_list[left_list_index])
left_list_index += 1
return sorted_list
def merge_sort(nums):
# If the list is a single element, return it
if len(nums) <= 1:
return nums
# Use floor division to get midpoint, indices must be integers
mid = len(nums) // 2
# Sort and merge each half
left_list = merge_sort(nums[:mid])
right_list = merge_sort(nums[mid:])
# Merge the sorted lists into a new one
return merge(left_list, right_list)
# Verify it works
random_list_of_nums = [120, 45, 68, 250, 176]
random_list_of_nums = merge_sort(random_list_of_nums)
print(random_list_of_nums)
merge_sort()` 関数は、これまでのソートアルゴリズムとは異なり、既存のリストをソートするのではなく、ソートされた新しいリストを返すことに注意してください。
したがって、マージソートは入力リストと同じサイズの新しいリストを作成するためのスペースを必要とします。
時間的複雑性
まず最初に merge 関数を見てみましょう。この関数は 2 つのリストを受け取り、n 回反復処理します。ここで、n は 2 つのリストを合わせた入力のサイズです。
merge_sort` 関数は、与えられた配列を 2 つに分割し、再帰的にその部分配列をソートします。再帰的にソートされる入力は与えられた入力の半分であるため、バイナリツリーと同様に処理にかかる時間は n に対して対数的に大きくなります。
したがって、マージソートアルゴリズムの全体的な時間計算量はO(nlog(n))となります。
クイックソート
この分割統治アルゴリズムは、この記事で扱うソートアルゴリズムの中で最もよく使われるものです。正しく設定すれば、非常に効率的で、マージソートが使用する余分なスペースは必要ありません。ピボット要素を中心にリストを分割し、ピボットを中心に値を並べ替えます。
説明
クイックソートは、まずリストを分割して、ソートされる場所にあるリストの値を1つ選びます。この値はピボットと呼ばれます。ピボットより小さい要素はすべて、その左に移動します。大きい要素はすべて右に移動します。
ピボットが正しい位置にあることを確認したら、リスト全体がソートされるまで、ピボットを中心に値を再帰的にソートします。
クイックソートの詳細な解説記事を読みたい方は、こちらをご覧ください。
実装
# There are different ways to do a Quick Sort partition, this implements the
# Hoare partition scheme. Tony Hoare also created the Quick Sort algorithm.
def partition(nums, low, high):
# We select the middle element to be the pivot. Some implementations select
# the first element or the last element. Sometimes the median value becomes
# the pivot, or a random one. There are many more strategies that can be
# chosen or created.
pivot = nums[(low + high) // 2]
i = low - 1
j = high + 1
while True:
i += 1
while nums[i] < pivot:
i += 1
j -= 1
while nums[j] > pivot:
j -= 1
if i >= j:
return j
# If an element at i (on the left of the pivot) is larger than the
# element at j (on right right of the pivot), then swap them
nums[i], nums[j] = nums[j], nums[i]
def quick_sort(nums):
# Create a helper function that will be called recursively
def _quick_sort(items, low, high):
if low < high:
# This is the index after the pivot, where our lists are split
split_index = partition(items, low, high)
_quick_sort(items, low, split_index)
_quick_sort(items, split_index + 1, high)
_quick_sort(nums, 0, len(nums) - 1)
# Verify it works
random_list_of_nums = [22, 5, 1, 18, 99]
quick_sort(random_list_of_nums)
print(random_list_of_nums)
時間的複雑性
最悪のケースは、最小または最大の要素が常にピボットとして選択される場合である。この場合、サイズn-1のパーティションが作成され、再帰的な呼び出しがn-1回発生することになります。このため、最悪の場合の時間計算量はO(n^2)となります。
これは最悪のケースですが、クイックソートは平均的な時間計算量がはるかに速いため、多用されています。Partition関数はネストしたwhile` ループを利用しますが、入れ替えを行うために配列のすべての要素で比較を行います。そのため、時間計算量はO(n)です。
良いピボットがあれば、クイックソート関数は配列を半分に分割し、それは n に対して対数的に増加します。したがって、クイックソートアルゴリズムの平均的な計算量は O(nlog(n)) となります。
Pythonの組み込みソート関数
これらのソートアルゴリズムを理解することは有益ですが、ほとんどのPythonプロジェクトでは、この言語ですでに提供されているソート関数を使うことになるでしょう。
リストがソートされるようにするには、 sort() メソッドを使います。
apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2]
apples_eaten_a_day.sort()
print(apples_eaten_a_day) # [1, 1, 1, 2, 2, 2, 3]
あるいは、 sorted() 関数を使って新しいソートされたリストを作成することもできます。
apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2]
sorted_apples = sorted(apples_eaten_a_day_2)
print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3]
どちらも昇順でソートされますが、 reverse フラグを True に設定することで簡単に降順にソートすることができます。
# Reverse sort the list in-place
apples_eaten_a_day.sort(reverse=True)
print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1]
# Reverse sort to get a new list
sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True)
print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1]
私たちが作成したソートアルゴリズム関数とは異なり、これらの関数はどちらもタプルのリストやクラスのリストをソートすることができます。sorted()` 関数は、リスト、文字列、タプル、辞書、セット、そしてあなたが作成したカスタムイテレータを含む、あらゆるイテレート可能なオブジェクトをソートすることができます。
これらのソート関数は Tim Sort アルゴリズムを実装しており、Merge Sort と Insertion Sort に触発されたアルゴリズムである。
速度比較
各アルゴリズムの処理速度を知るために、0から1000までの5000個の数値のリストを作成する。そして、各アルゴリズムが完了するまでの時間を計る。これを10回繰り返すことで、より確実に性能のパターンを確立することができます。
結果は以下の通りです。時間は秒単位です。
| 実行｜バブル｜選択｜挿入｜ヒープ｜マージ｜クイック｜—-。
| — | — | — | — | — | — | — |
| 1 | 5.53188 | 1.23152 | 1.60355 | 0.04006 | 0.02619 | 0.01639 |
| 2 | 4.92176 | 1.24728 | 1.59103 | 0.03999 | 0.02584 | 0.01661 |
| 3 | 4.91642 | 1.22440 | 1.59362 | 0.04407 | 0.02862 | 0.01646 |
| 4 | 5.15470 | 1.25053 | 1.63463 | 0.04128 | 0.02882 | 0.01860 |
| 5 | 4.95522 | 1.28987 | 1.61759 | 0.04515 | 0.03314 | 0.01885 |
| 6 | 5.04907 | 1.25466 | 1.62515 | 0.04257 | 0.02595 | 0.01628 |
| 7 | 5.05591 | 1.24911 | 1.61981 | 0.04028 | 0.02733 | 0.01760 |
| 8 | 5.08799 | 1.25808 | 1.62603 | 0.04264 | 0.02633 | 0.01705 |
| 9 | 5.03289 | 1.24915 | 1.61446 | 0.04302 | 0.03293 | 0.01762 |
| 10 | 5.14292 | 1.22021 | 1.57273 | 0.03966 | 0.02572 | 0.01606 |
| 平均値｜5.08488｜1.24748｜1.60986｜0.04187｜0.02809｜0.01715｜となります。
自分でテストをセットアップすれば異なる値が得られるでしょうが、観察されるパターンは同じか類似しているはずです。バブルソートはすべてのアルゴリズムの中で最も遅く、最も悪いパフォーマンスです。ソートやアルゴリズムの入門用としては有用ですが、実用には適さないでしょう。
また、クイックソートは非常に高速で、マージソートの約2倍の速さであり、実行にそれほど多くのスペースを必要としないことに気づきました。今回の分割はリストの中央の要素に基づいて行われましたが、分割が異なれば結果も異なる可能性があることを思い出してください。
挿入ソートは選択ソートよりもはるかに少ない比較しか行わないため、通常、実装はより速くなりますが、今回の実行では選択ソートの方がわずかに速くなりました。
挿入ソートは選択ソートよりも多くのスワップを行います。もし値のスワップが値の比較よりもかなり多くの時間を消費するのであれば、この「逆の結果」はもっともでしょう。
ソートアルゴリズムを選択する際には、環境に配慮することがパフォーマンスに影響します。
結論
ソートのアルゴリズムは、データを並べ替えるための様々な方法を提供してくれます。我々は6つの異なるアルゴリズム、バブルソート、選択ソート、挿入ソート、マージソート、ヒープソート、クイックソートとそれらのPythonでの実装を調べました。
アルゴリズムが実行する比較と交換の量と、コードが実行される環境は、性能を決定する重要な要因です。実際のPythonアプリケーションでは、入力の柔軟性と速度のために、Pythonに組み込まれたソート関数にこだわることが推奨されます。