[Pythonアルゴリズム]ソート


ツールバーの


:データを特定の基準で順番にリストする
  • 「アルゴリズムの効率」は分かりやすい.
  • 異なる並べ替えアルゴリズムを理解し、同じ問題を理解するには多くのアルゴリズムが解決できない可能性がある.各アルゴリズムの性能を比較することによって、アルゴリズムの性能分析を理解する.
  • Pythonのソートライブラリ


    sorted() VS .sort()


    ソート()関数
  • 連結ソートに基づく関数
  • リスト、ディクソン資料型などを入力し、
  • のソート結果を出力する
  • グループまたはディクソンデータ型を入力と、リストデータ型
  • が返されます.
    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    result = sorted(array)
    print(result)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    print(array)
    # [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    .sort()リストオブジェクトの組み込み関数
  • は個別のソートのリストを返さず、内部要素は
  • にソートされた.
    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    array.sort()
    print(array)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    ソート・ライブラリの時間的複雑さ


    最悪の場合でも,
  • は時間的複雑度O(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)を保証できる.
  • バブルソート(Bubble Sort)


    Idea

  • の2つの隣接するデータを比較してシフトする
    注意:https://visualgo.net/en/sorting

  • ソース:https://en.wikipedia.org/wiki/Bubble_sort

    How To

  • 隣接する2つのデータを比較する
  • 前のデータが後のデータより大きい場合、シフト
  • Code

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    for i in range(len(array)-1):
        for j in range(len(array)-i-1):
            if array[j] > array[j+1]:  # 두개의 인접 데이터 비교
                array[j], array[j+1] = array[j+1], array[j]  # swap
                
    print(array)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    Analysis

  • 時間複雑度=O(N 2)O(N^2)O(N 2)
  • 完全順序付けの最適時間複雑度=O(N)O(N)O(N)
  • 選択ソート(Selection Sort)


    Idea

  • 毎回「最小を選択」
    注意:https://visualgo.net/en/sorting

  • ソース:https://en.wikipedia.org/wiki/Selection_sort

    How To

  • 最小のデータ置換前のデータ
  • を選択する.
  • を繰り返し、小さいデータを前の2番目のデータに置き換えます.

    Code

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    for i in range(len(array)):
        min_idx = i  # 가장 작은 원소의 인덱스
        for j in range(i+1, len(array)):
            if array[min_idx] > array[j]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]  # Swap
        
    print(array)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    Analysis

  • 時間複雑度=O(N 2)O(N^2)O(N 2)
    1.N-1は最小の数字を見つけて一番前に送る必要があります
    2.小数を検索するたびに比較演算が必要
  • ソートの挿入(Insertion Sort)


    Idea

  • データを1つずつチェックし、各データを適切な位置に「挿入」する.
  • 「ほぼ整列したデータ」を必要とせずに、必要に応じて再配置を行います.
    注意:https://visualgo.net/en/sorting

  • ソース:https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

    How To

  • は、2番目のインデックスから
  • を開始する.
  • インデックス(キー値)の前のデータ(B)からキーの比較を開始する 値が小さい場合は、B値をポストインデックス
  • にコピーします.
  • キー より大きなデータに遭遇するまで値を繰り返し、キー値を大きなデータの後の位置
  • に移動する.

    Code

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    for i in range(1, len(array)):
        for j in range(i, 0, -1):  # i부터 1까지 역으로 확인
            if array[j] < array[j-1]:  # 자기보다 크다면 한 칸씩 왼쪽으로 이동
                array[j], array[j-1] = array[j-1], array[j]
            else:  # 자기보다 작은 수를 만나면 멈춤
                break
                
    print(array)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    

    Analysis

  • 時間複雑度=O(N 2)O(N^2)O(N 2)
  • 現在のリストのデータがほぼソートされている場合、実行速度は非常に速い
    -完全整列時の時間的複雑度=O(N)O(N)O(N)O(N)