Python-ソートアルゴリズム

並べ替えとは、特定の形式でデータを配置することです。並べ替えアルゴリズムは、特定の順序でデータを配置する方法を指定します。最も一般的な順序は、数字順または辞書順です。

ソートの重要性は、データがソートされた方法で保存されている場合、データ検索を非常に高いレベルに最適化できるという事実にあります。ソートは、より読みやすい形式でデータを表すためにも使用されます。以下に、Pythonでのこのようなソートの実装を5つ示します。

バブルソート
ソートのマージ
挿入ソート
シェルソート
選択ソート

バブルソート

これは比較ベースのアルゴリズムであり、隣接する要素の各ペアが比較され、順序が正しくない場合は要素が交換されます。

def bubblesort(list):

# Swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

上記のコードが実行されると、次の結果が生成されます-

[2, 6, 11, 19, 27, 31, 45, 121]

ソートのマージ

マージソートは、最初に配列を等しい半分に分割してから、ソートされた方法でそれらを結合します。

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# Find the middle point and devide it
    middle = len(unsorted_list)//2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

上記のコードが実行されると、次の結果が生成されます-

[11, 12, 22, 25, 34, 64, 90]

挿入ソート

挿入ソートには、ソートされたリスト内の指定された要素に適切な場所を見つけることが含まれます。そのため、最初に最初の2つの要素を比較し、それらを比較して並べ替えます。次に、3番目の要素を選択し、前の2つの並べ替えられた要素の中から適切な位置を見つけます。このようにして、適切な位置に要素を配置することで、既にソートされたリストに要素を徐々に追加していきます。

def insertion_sort(InputList):
    for i in range(1, len(InputList)):
        j = i-1
        nxt_element = InputList[i]
# Compare the current element with next one

        while (InputList[j] > nxt_element) and (j >= 0):
            InputList[j+1] = InputList[j]
            j=j-1
        InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

上記のコードが実行されると、次の結果が生成されます-

[2, 11, 19, 27, 30, 31, 45, 121]

シェルソート

Shell Sortには、ech otherから離れた要素のソートが含まれます。特定のリストの大きなサブリストをソートし、すべての要素がソートされるまでリストのサイズを縮小します。以下のプログラムは、リストサイズの長さの半分にそれを等しくすることによってギャップを見つけ、その中のすべての要素のソートを開始します。次に、リスト全体がソートされるまで、ギャップをリセットし続けます。

def shellSort(input_list):

    gap = len(input_list)//2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# Sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# Reduce the gap for the next element

        gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

上記のコードが実行されると、次の結果が生成されます-

[2, 11, 19, 27, 30, 31, 45, 121]

選択ソート

選択ソートでは、指定されたリスト内の最小値を見つけて、それをソートされたリストに移動することから始めます。次に、ソートされていないリスト内の残りの要素ごとにプロセスを繰り返します。ソートされたリストに入る次の要素は、既存の要素と比較され、正しい位置に配置されます。そのため、最後に、ソートされていないリストのすべての要素がソートされます。

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# Swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

上記のコードが実行されると、次の結果が生成されます-

[2, 11, 19, 27, 30, 31, 45, 121]

Python-data-structure-python-sorting-algorithms

目次

Python-ソートアルゴリズム

バブルソート

ソートのマージ

挿入ソート

シェルソート

選択ソート