挿入ソートアルゴリズム

挿入ソートの定義

挿入ソートは、トランプをソートするプロセスのように機能するソート アルゴリズムの一種で、配列を 2 つの部分、ソートされた数字の一部とソートされていない数字、間違った順序の数字 (に存在する数字) に分割します.未ソート部分 ) がソート済み部分の正しい位置に挿入されます.

挿入ソートの時間と空間の複雑さ

時間の複雑さ
スペースの複雑さ


O(n2)
O(1)

例を使ったアルゴリズム説明

ソートされていない配列 [7,4,12,3] があるとします.
ソートされた部分は 7 (ボールド スタイル)、ソートされていない部分は 4 から 3 (イタリック スタイル) です.

(4 < 7) そのため、ソートされた部分で 7 の前に 4 を挿入します.
したがって、配列は [4,7,12,3]

になります.

(12 > 7) したがって、同じ位置に保持されるため、配列は [4,7,12,3]

になります.

3 は 12,7 および 4 より小さいため、最初の位置になるため、最終的な配列は [3,4,7,12]

pythonを使った挿入ソートアルゴリズムの実装

Python に慣れていない場合は、他のプログラミング言語での挿入ソート アルゴリズムの実装を見つけることができます.

javascript

c++

c#

java

php

=> パイソン:

def insertionSort(items: list) -> list:
    """
        [ name ]            => insertion sort
        [ type ]            => sorting algorithms
        [ time complexity ] => O(n^2)
        [ space complexity ]=> O(1)
        [ params ]          => (items) list to sort
        [ return ]          => sorted list
        [ code reference link ] => ("https://www.geeksforgeeks.org/insertion-sort/")       
    """
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and key < items[j] :
                items[j + 1] = items[j]
                j -= 1
        items[j + 1] = key
    return array

リファレンスと役立つリソース

https://www.geeksforgeeks.org/insertion-sort/

https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm

geeksforgeeks に感謝します.
良い一日を過ごしてください :)
#day_9