複数のアルゴリズム2

前回の授業では,種々のアルゴリズムを例に線形ナビゲーションとバイナリナビゲーションを紹介した.このレッスンでは、別のアルゴリズムを例にソートについて説明します.

👮ソート(ソート)

ソートは、リスト内の要素を特定の順序でソートします.昇順と降順はよく聞いたことがあるはずです.この2つの方法はいずれも特定の順序に適用される.
実際には、リストを前に学習するときに、関数のソートとを内蔵します.sort()メソッド.この二つの概念を利用すればいいのに、どうしてソートを学ばなければならないのですか.
アルゴリズムの定義を説明し、アルゴリズムをコードとして実装する際に組み込み関数の使用をできるだけ避けます.これはアルゴリズムを実装することによって問題解決の基礎を築くためである.
ソートはアルゴリズムの基礎です.また,これもすべての開発者が知っておくべき最も基本的なアルゴリズムである.したがって、コードを使用してソートを直接実装する方法を理解することは、開発者が完了しなければならないタスクです.
ソートには多くのアルゴリズムがありますが、まず2つの状況しか勉強しません.

👮‍♀️ ソートの選択

まず、「ソートの選択」(Selection Sort)について説明します.選択ソートは最も自然なソートアルゴリズムです.とても直感的です.
最小値を0番のインデックスに配置し、小さな値を見つけ、1番のインデックスを見つけ、小さな値を見つけ、2番のインデックスを見つけます...このように並べ替えます.
リストの例を見てみましょう.

some_list = [4, 7, 5, 2, 6, 9]

上のリストに選択ソートを適用してみます.インデックス0から順にご覧ください.0番インデックスには最大値が含まれている必要があります.起点を基準にすると、4は最小の値です.
次に、1番のインデックスを表示すると、7が表示されます.4は7未満であるため、4は依然として最大値である.このリストでは、4は2が現れるまで最上位を維持し、2が現れると最上位は2になります.
次に、0番のインデックスの値4と3番のインデックスの値2がリストに置き換えられます.これは、値が2より小さくないためです.これにより、インデックス0の2が最大になります.

some_list = [2, 7, 5, 4, 6, 9]

0番のインデックスに値が指定されました.次の値を検索して1番のインデックスに入ります.1～5番のインデックスを見てみましょう.1番目のインデックスの7は、次のインデックスの5に遭遇すると、最高値を返します.
同様に、5は4に出会った瞬間に席を譲り、その後はより小さな値はありません.結果は4が1番インデックスに入ります.

some_list = [2, 4, 7, 5, 6, 9]

2つの数値間の相対数が基数より小さい場合は、インデックスをスキップして置き換えることができます.この手順を繰り返すと、最終的に次のリストが完了します.最後のインデックスは最高値になります.

some_list = [2, 4, 5, 6, 7, 9]

要するに、選択ソートは、各位置の値を検索するソートです.
選択ソートを実施するコードとその例を示すことに注意してください.

def selection_sorting(my_list):

    for i in range(len(my_list)-1):
        min_index = i

        for j in range(i+1, len(my_list)):
            if my_list[j] < my_list[min_index]:
                min_index = j

        temp = my_list[i]
        my_list[i] = my_list[min_index]
        my_list[min_index] = temp

    return my_list

print(selection_sorting([4, 7, 5, 2, 6, 9]))

[2, 4, 5, 6, 7, 9]

👮‍♀️ 整列挿入

2つ目は「挿入ソート」(InsertionSort)です.挿入位置合わせは、選択位置合わせとは異なり、各値が入る位置を検索します.値ではなく位置を見つけなければなりません.
トランプゲームを例に挙げる.すでにソートされたインデックスを持っていて、相手は新しい番号のカードをあなたに渡しました.並べ替えられたインデックス間で適切な位置を選択し、新しいカードを入れます.
リストの例を見てみましょう.

some_list = [4, 7, 5, 2, 6, 9]

まず、7を基準数とします.まず7の後部座席を見る必要はありません4と7より7の方が大きいので変化はありません.

some_list = [4, 7]

今から5まで範囲を広げてみましょう.7は5より小さいので、7を右側の1マスに移動し、7が欠けている空きスペースに5を入れればいいです.

some_list = [4, 5, 7]

次に範囲を2に拡大します.5に比べて、2が小さいため、5を右側のグリッドに移動します.2は4および7より小さいので、4および7グリッドを右側に移動します.では、インデックス0は空ですよね?その位置に2を置けばいいです

some_list = [2, 4, 5, 7]

基数と相対数を最後のインデックスに比較し、より大きな値を得た場合は、スペースを右に移動し、空白に基数を入れるだけです.

some_list = [2, 4, 5, 6, 7, 9]

ソートを挿入するコードとその例を見てみましょう.

def insertion_sorting(my_list):

    for end in range(1, len(my_list)):
    
        for i in range(end, 0, -1):
            if my_list[i-1] > my_list[i]:
                temp = my_list[i-1]
                my_list[i-1] = my_list[i]
                my_list[i] = temp

    return my_list

print(insertion_sorting([4, 7, 5, 2, 6, 9]))

[2, 4, 5, 6, 7, 9]

👮‍♀️ ソートアルゴリズムの比較

この2つの方法に加えて、「シリアル」、「スタック」、「バブル」などのソートアルゴリズムもあります.しかし、こんなに多くのソートアルゴリズムの中で、最も有効なのはどのソートですか?
このサイトは、複数のソート効率を提供します.

たとえば、ほとんどソート状態にあるリストをソートする場合、ソート速度が最も速く、ソート順序がランダムなリストを挿入する場合、ソート速度が最も速いのは「hip」です.
逆にソートされたリストでは、ソートを挿入するのに時間がかかります.ソートおよびマージ・プロシージャの選択は、状況の影響を受けず、時間がかかります.
要するに、ソートには絶対的な良い答えはありません.場合によっては、各アルゴリズムにはメリットとデメリットがあるからです.これらのアルゴリズムを学習する際には,問題を解決するだけでなく,アルゴリズム自体の効率を評価しなければならない.

* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.