面接の質問に必ず読むべき一冊！ Python のトップ 5 ソートアルゴリズムとその実装コード

ソートは、すべての IT エンジニアと開発者にとって不可欠な知識スキルです。コーディング面接に合格するだけでなく、アルゴリズム自体も理解する必要があります。さまざまなソートアルゴリズムは、アルゴリズムの設計がプログラムの複雑さ、速度、効率に大きな影響を与える可能性があることを示す良い例です。

面接でよく聞かれる最も一般的なソートアルゴリズムのトップ 5 を見て、それらを Python で実装する方法を見てみましょう。

1. バブルソート

バブルソートは、ソートの仕組みを明確に示しながらもシンプルで理解しやすいため、入門レベルの CS コースで最もよく教えられているソートです。バブルソートはリストを順に進み、隣接する要素のペアを比較します。要素の順序が間違っている場合は、入れ替えられます。リストがソートされるまで、リストのソートされていない部分の走査を繰り返します。バブルソートはリストのソートされていない部分を繰り返し通過するため、最悪の場合の複雑さは O(n²) になります。

バブルソートを定義します。
    定義 swap(i, j):
        arr[i]、arr[j] = arr[j]、arr[i] 
 
    n = 長さ(arr)
    交換 = True   
     
    x = -1
    交換中:
        交換 = False  
        x = x + 1
 iが範囲(1, nx)内にある場合:
            arr[i - 1] > arr[i]の場合:
                スワップ(i - 1, i)
                交換 = True   
                     
リターン

2. 選択ソート

選択ソートも非常に単純で、バブルソートよりも優れています。 2 つから選択する必要がある場合は、デフォルトの「右選択ソート」を使用するのが最適です。選択ソートを使用して、入力リスト/配列を 2 つの部分に分割します。1 つはソートされた項目のサブリスト、もう 1 つはリストの残りを構成する残りの項目のサブリストです。

まず、ソートされていないサブリスト内の最小の要素を見つけて、それをソートされたサブリストの最後に配置します。したがって、最小のソートされていない要素を取得し、ソートされた順序でソートされたサブリストに格納し続けます。リストが完全にソートされるまでこのプロセスが繰り返されます。

 def selection_sort(arr):
 iが範囲内(len(arr))の場合:
        最小値 = i 
         
 jが範囲(i + 1, len(arr))内にある場合:
            # 最小値を選択
            arr[j] < arr[最小値]の場合:
                最小値 = j 
 
        # ソートされた配列の最後に置く
        arr[最小値]、arr[i] = arr[i]、arr[最小値] 
             
リターン

3. 挿入ソート

挿入ソートはバブルソートや選択ソートよりも高速で、よりシンプルであると言えます。カードゲームをプレイするときと同じように、カードをシャッフルするプロセスは挿入ソートの繰り返しです。ループの各反復で、挿入ソートは配列から 1 つの要素を削除します。次に、他のソートされた配列内でその要素が属する位置を検索し、そこに挿入します。入力要素がなくなるまでこのプロセスを繰り返します。

 def inserting_sort(arr): 挿入ソート
         
 iが範囲内(len(arr))の場合:
カーソル= arr[i]
        位置 = 私
         
        pos > 0かつarr[pos - 1] >カーソルの場合:
            # リスト内の数字を入れ替える
            arr[位置] = arr[位置 - 1]
            位置 = 位置 - 1
        # 中断して最終的なスワップを行う
        arr[pos] =カーソル  
 
リターン

4. マージソート

マージソートは分割統治アルゴリズムの完璧な例です。このアルゴリズムを使用するには、主に次の 2 つの手順だけが必要です。

(1) ソートされていないリストを、それぞれが 1 つの「ソートされていない」要素を持つ N 個のサブリストになるまで分割し続けます。ここで、N は元の配列の要素数です。

（２）繰り返しマージ、つまり、２つのサブリストを一度にマージして、すべての要素がソートされた配列に完全にマージされるまで、新しいソートされたサブリストを生成する。

 def merge_sort(arr):
    # 最後の配列を分割する
    len(arr) <= 1の場合:
リターン
    中間 = len(arr) // 2
    # 両方の部分で再帰的にmerge_sortを実行します
左、右= merge_sort(arr[:mid]), merge_sort(arr[mid:]) 
 
    # 一緒にマージする
merge( left , right ,arr.copy())を返します
 
 
 def merge(左、右、 マージ済み ): 
 
    左カーソル、右カーソル = 0, 0
    left_cursor < len( left )かつright_cursor < len( right ) の場合: 
       
        # それぞれをソートして結果に入れる
        左[左カーソル] <=右[右カーソル] の場合:
            結合[左カーソル+右カーソル]=左[左カーソル]
            左カーソル += 1
それ以外：
            結合された[左カーソル + 右カーソル] =右[右カーソル]
            右カーソル += 1 
             
 left_cursorがrange(left_cursor, len( left ))内にある場合:
        結合された[左カーソル + 右カーソル] =左[左カーソル] 
         
 right_cursor がrange(right_cursor, len( right ))内にある場合:
        結合された[左カーソル + 右カーソル] =右[右カーソル] 
 
マージされたリターン

5. クイックソート

クイックソートも、マージソートと同様に分割統治アルゴリズムです。少し複雑ではありますが、ほとんどの標準実装ではマージソートよりもはるかに高速に実行され、最悪の場合でも O(n²) の複雑度に達することはほとんどありません。主なステップは 3 つあります。

（１）まず配列からピボットと呼ばれる要素を選択します。

（２）軸より小さい要素はすべて軸の左に移動し、軸より大きい要素はすべて軸の右に移動します。これをパーティション操作と呼びます。

（３）前の軸の値より小さいか大きい値を持つ要素の各サブ配列に対して、上記２つの手順を再帰的に適用する。

 defパーティション(配列、開始、終了):
    pivot_idx =開始 
 i がxrange( begin +1, end +1)内にある場合:
        配列[i] <= 配列[ begin ]の場合:
            ピボットIDx += 1
            配列[i]、配列[pivot_idx] = 配列[pivot_idx]、配列[i]
    配列[pivot_idx]、配列[ begin ] = 配列[ begin ]、配列[pivot_idx]
 pivot_idxを返す
 
 def quick_sort_recursion(配列、 begin 、 end ):
    開始>=終了の場合:
戻る 
    pivot_idx = パーティション(配列、開始、終了)
    quick_sort_recursion(配列、 begin 、pivot_idx-1)
    quick_sort_recursion(配列、pivot_idx+1、終了) 
 
 def quick_sort(配列、開始= 0、終了= None):
    終了の場合 なし:
 end = len(配列) - 1 
     
 quick_sort_recursion(配列、 begin 、 end )を返す