詳細な並べ替えアルゴリズム（Pythonで実装）
Pythonの組み込みの並べ替えアルゴリズム＃
他の多くの高レベルプログラミング言語と同様に、Python言語は、 sorted（）関数を使用してデータをすぐに使用する機能を提供します。例：
>>> li =[9,5,3,6,7]>>>sorted(li)[3,5,6,7,9]
バブルソート＃
バブルソートは、最も簡単なソートアルゴリズムの1つです。その名前は、アルゴリズムの動作方法に由来しています。都合がよいと、リストの最大の要素が正しい位置に「バブル」します。
バブルソートでは、リストをトラバースし、要素を一度に比較し、不規則な隣接アイテムを交換します。
Pythonはバブルソートを実装します##
def bublle_sort(array):
n =len(array)for i inrange(n):
# フラグを作成する
already_sorted = True
for j inrange(n - i -1):if array[j]> array[j+1]:
array[j], array[j+1]= array[j+1], array[j]
already_sorted = False
if already_sorted:breakreturn array
時間の複雑さ：O（
).
挿入ソート＃
バブルソートと同様に、挿入ソートアルゴリズムは実装と理解が簡単です。ただし、バブルソートとは異なり、各アイテムをリストの残りの部分と比較し、正しい位置に挿入することにより、一度に1つずつソートされたリスト要素を作成します。この「挿入」プロセスは、アルゴリズムに名前を付けます。
挿入の並べ替えを説明する良い例は、カードのデッキを並べ替える方法です。手にカードのセットがあり、それらを順番に並べたいと想像してください。まず、正しい位置が見つかるまで、1枚のカードを残りのカードと比較します。そのとき、カードを正しい位置に挿入してから、新しいカードの作成を再開し、手にあるすべてのカードがソートされるまで繰り返す必要があります。
Pythonは挿入ソートを実装します##
def insertion_sort(array):for i inrange(1,len(array)):
key_item = array[i]
j = i -1while j >=0 and array[j]> key_item:
array[j +1]= array[j]
j -=1
array[j +1]= key_item
return arry
時間の複雑さ：O（
).
マージソート##
マージソートは非常に効果的なソートアルゴリズムです。これは、複雑な問題を解決するための強力なアルゴリズム手法である除算と征服の方法に基づいています。
分裂と征服を正しく理解するためには、最初に再帰の概念を理解する必要があります。再帰には、問題が解決できないほど小さくなるまで、問題をより小さなサブ問題に分解することが含まれます。プログラミングでは、再帰は通常、それ自体を呼び出す関数によって表されます。
分割と征服のアルゴリズムは通常、同じ構造に従います。
- 元の入力はいくつかの部分に分割され、各部分はサブ問題を表します。これは元の入力と似ていますが、より単純です。
- 各サブ問題は再帰的に解決されます。
- すべてのサブ問題の解決策は、全体的な解決策にまとめられます。
マージソートの場合、divide and conquerメソッドは、入力値のセットを2つの等しい部分に分割し、各半分を再帰的にソートし、最後に2つのソートされた部分をソート済みリストにマージします。
Python実装マージ##
def merge(left, right):iflen(left)==0:return right
iflen(right)==0:return left
result =[]
index_left = index_right =0whilelen(result)<len(left)+len(right):if left[index_left]<= right[index_right]:
result.append(left[index_left])
index_right +=1else:
result.append(right[index_right])
index_left +=1if index_right ==len(right):
result += left[index_left:]breakif index_left ==len(left):
result += right[index_right:]breakreturn result
def merge_sort(array):iflen(array)<2:return array
midpoint =len(array)// 2returnmerge(
left=merge_sort(array[:midpoint]),
right=merge_sort(array[midpoint:]))
時間の複雑さ：O（
)
クイックソート＃
マージソートと同様に、クイックソートアルゴリズムは、除算と征服の原理を使用して、入力配列を2つのリストに分割します。最初のリストには小さなアイテムが含まれ、2番目のリストには大きなアイテムが含まれます。次に、アルゴリズムは、結果のリストが完全にソートされるまで、2つのリストを再帰的にソートします。
入力リストを分割することを、リストの分割と呼びます。クイックソートは最初にピボット要素を選択し、次にそのピボットの周りにリストを分割して、小さい各要素を低い配列に配置し、大きい各要素を高い配列に配置します。
下位リストの各要素をPivotTableの左側に配置し、上位リストの各要素をPivotTableの右側に配置して、最終的にソートされたリストの必要な場所に正確に配置します。これは、リスト全体がソートされるまで、関数が再帰的に低から高に再帰的に移動できることを意味します。
Pythonはクイックソートを実装しています##
rom random import randint
def quicksort(array):
# If the input array contains fewer than two elements,
# then return it as the result of the functioniflen(array)<2:return array
low, same, high =[],[],[]
# Select your `pivot` element randomly
pivot = array[randint(0,len(array)-1)]for item in array:
# Elements that are smaller than the `pivot` go to
# the `low` list. Elements that are larger than
# ` pivot` go to the `high` list. Elements that are
# equal to `pivot` go to the `same` list.if item < pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)
# The final result combines the sorted `low` list
# with the `same` list and the sorted `high` list
returnquicksort(low)+ same +quicksort(high)
時間の複雑さ：O（
)
Timsort algorithm
Timsortアルゴリズムは、挿入ソートとマージソートの両方の長所を使用するため、ハイブリッドソートアルゴリズムと見なされます。 Timsortは、2002年にTim Petersによって作成され、Python言語の標準の並べ替えアルゴリズムとして使用されているため、Pythonコミュニティに近いです。
Timsortの主な機能は、ほとんどの実際のデータセットに存在するソートされた要素を利用することです。これらは自然な操作と呼ばれます。次に、アルゴリズムはリストをトラバースし、要素を実行に収集して、ソートされたリストにマージします。
PythonはTimsortを実装します##
このセクションでは、Timsortアルゴリズムのすべての部分を説明する最低限のPython実装を作成します。興味があれば、Timsortの[元のC実装]（https://links.jianshu.com/go?to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fblob%2Fmaster%2FObjects%2Flistobject.c）を確認することもできます。
def insertion_sort(array, left=0, right=None):if right is None:
right =len(array)-1
# Loop from the element indicated by
# ` left` until the element indicated by `right`for i inrange(left +1, right +1):
# This is the element we want to position in its
# correct place
key_item = array[i]
# Initialize the variable that will be used to
# find the correct position of the element referenced
# by `key_item`
j = i -1
# Run through the list ofitems(the left
# portion of the array) and find the correct position
# of the element referenced by `key_item`. Do this only
# if the `key_item` is smaller than its adjacent values.while j >= left and array[j]> key_item:
# Shift the value one position to the left
# and reposition `j` to point to the next element
# ( from right to left)
array[j +1]= array[j]
j -=1
# When you finish shifting the elements, position
# the `key_item`in its correct location
array[j +1]= key_item
return array
この変更された実装では、配列のどの部分をソートする必要があるかを示す2つの左右のパラメーターが追加されます。これにより、Timsortアルゴリズムで配列の一部をソートできます。新しい関数を作成する代わりに関数を変更すると、挿入ソートとTimsortの両方に使用できるようになります。
def timsort(array):
min_run =32
n =len(array)
# Start by slicing and sorting small portions of the
# input array. The size of these slices is defined by
# your `min_run` size.for i inrange(0, n, min_run):insertion_sort(array, i,min((i + min_run -1), n -1))
# Now you can start merging the sorted slices.
# Start from`min_run`, doubling the size on
# each iteration until you surpass the length of
# the array.
size = min_run
while size < n:
# Determine the arrays that will
# be merged together
for start inrange(0, n, size *2):
# Compute the `midpoint`(where the first array ends
# and the second starts) and the `endpoint`(where
# the second array ends)
midpoint = start + size -1
end =min((start + size *2-1),(n-1))
# Merge the two subarrays.
# The `left` array should go from`start` to
# ` midpoint + 1`,while the `right` array should
# go from`midpoint + 1` to `end + 1`.
merged_array =merge(
left=array[start:midpoint +1],
right=array[midpoint +1:end +1])
# Finally, put the merged array back into
# your array
array[start:start +len(merged_array)]= merged_array
# Each iteration should double the size of your arrays
size *=2return array
この変更された実装では、配列のどの部分をソートする必要があるかを示す2つの左右のパラメーターが追加されます。これにより、Timsortアルゴリズムで配列の一部をソートできます。新しい関数を作成する代わりに関数を変更すると、挿入ソートとTimsortの両方に使用できるようになります。
Recommended Posts