[CS 50]アルゴリズム-ソートアルゴリズムの実行時間

ソートアルゴリズムの実行時間
学習目標
複数の並べ替えアルゴリズムおよび探索アルゴリズムの実行時間は、BigOおよびBigΩとして定義することができる.
キーワード

Big O

Big Ω

これまで学んだ線形検索,バイナリ検索,Bubbleソート,選択ソートの実際の実行時間を整理する.
運転時間上限

O(n^2):選択ソート、泡ソート

O(n log n)

O(n):線形探索

O(logn):バイナリ検索

O(1)

運転時間下限

Ω(n^2):選択整列、泡整列

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1):線形探索、バイナリ探索

ここでは、バブルソートをよりよく行う方法について説明します.
並べ替えられた数字のリストをあげるとどうなりますか?
元のコードは以下の通りです.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

ここで,内環に交換が1つも起こらなければ,それはすでに整列している場合である.
したがって、外部ループは、「交換が発生しないまで」のみを実行するように変更できます.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

従って,最終Bubble配列の下限はΩ(n)であった.
場合によっては、ソートを選択するよりも速い方法です.
運転時間下限
Ω(n^2):ソート選択
Ω(n log n)
Ω(n):泡の位置合わせ
Ω(log n)
Ω(1):リニアサーチ、バイナリサーチ