『アルゴリズム』の初級ソートアルゴリズムまとめ

この文章は同時に私の個人ブログに収録します:『アルゴリズム』の初級ソートアルゴリズムの総括
ソートの選択
最も簡単なソートアルゴリズム:まず、配列の中で最も小さい要素を見つけて、次に、配列の中の最初の要素と位置を交換します.再び、残りの要素の中で最小の要素を見つけて、配列の2番目の要素と位置を変えます.このように往復して、配列全体が秩序化されていることを知っています.この方法は、残りの要素の中の最小者を絶えず選択しているため、選択ソートと呼ばれます.
交換のたびに1つの要素を並べ替えることができるので,交換の総回数はNである.したがって,アルゴリズムの時間効率は比較の回数に依存する.
特長

運転時間は入力に関係なく

データ移動は、最も少ない交換ごとに2つの配列要素の値が変更されるため、選択ソートにはN回の交換が使用される--交換回数と配列のサイズは線形関係(ほとんどのアルゴリズムは線形対数または二乗レベル)

具体コード

fun main(args: Array) {
    val a = arrayOf(1, 32, 2, 23, 5, 234, 12, 978, 2, 2, 0, 4)

    for (i in 0 until a.size) {
        var min=i
        for (j in i until a.size){
            if(a[j]<a[min]){
                min=j
            }
        }
        val t=a[i]
        a[i]=a[min]
        a[min]=t
    }

    a.forEach { print("$it ") }
}

ソートされたトラックの選択(交換されるたびに配列の内容)
画像はalgs 4から来ています.cs.princeton.edu
ソートの挿入
通常、トランプを整理する方法は1枚1枚で、各トランプを他の秩序あるトランプに挿入するのに適した位置です.コンピュータの実装では、挿入する要素に空間を空けるために、残りのすべての要素を挿入する前に右に1つ移動する必要があります.このアルゴリズムを挿入ソートと呼びます.
特長

は、選択ソートと同様に、現在のインデックスの左側のすべての要素が整列していますが、私の最終的な位置はまだ確定していません.より小さな要素に空間を空けるために、移動する可能性があります.インデックスが配列の右端に達すると、配列のソートが完了します.

の実行時間は、入力に関連しており、要素が基本的または秩序に近い配列をソートすることは、ランダムな配列または逆配列をソートするよりもずっと速い.

具体コード

fun main(args: Array) {
    val a = arrayOf(1, 32, 2, 23, 5, 234, 12, 978, 2, 2, 0, 4)

    for (i in 1 until a.size) {
        for (j in i downTo 1){
            if(a[j]<a[j-1]){
                val t=a[j]
                a[j]=a[j-1]
                a[j-1]=t
            }
        }
    }

    a.forEach { print("$it ") }
}

0からa.size−1の間の各iについて、a[i]とa[0]からa[i−1]の中のそれより小さいすべての要素を一度に秩序正しく交換する.インデックスiが左から右に変化する過程で、左側の要素は常に秩序化されるので、iが配列の右端に達するとソートが完了する.
ソートされたトラックを挿入(交換されるたびに配列の内容)
画像はalgs 4から来ています.cs.princeton.edu
ソートを挿入すると、部分的に整列した配列に非常に適しています.「部分的に整列」はどのように定義されますか?部分的に秩序化された配列のいくつかの典型的な表現:-配列内の各要素はその最終位置から遠くない.-秩序ある大きな配列と小さな配列.-配列内のいくつかの要素の位置が正しくありません.
ソートと選択ソートのトラックの比較図を挿入
画像はalgs 4から来ています.cs.princeton.edu
ヒルソート
ヒルソートは、挿入ソートに基づく高速ソートアルゴリズムであり、速度を速めるために挿入ソートを簡単に改善し、隣接しない要素を交換して配列の局所をソートし、最終的には挿入ソートで局所的に秩序化された配列をソートする.
特長
配列内の任意の間隔hの要素を秩序化します.このような配列をh秩序配列と呼ぶ.すなわち、1つのh秩序配列は、h個の互いに独立した秩序配列が織り込まれた配列である.
ソートを行うとき,hが大きいと,要素を遠くに移動し,より小さなh秩序を実現するために便利になる.このようにして,任意の1で終わるhシーケンスに対して配列を並べ替えることができる.
1つのh秩序配列(すなわち、h秩序サブ配列からなる配列)のピクチャはalgs 4から来る.cs.princeton.edu
ヒルソートの方法は、hサブ配列で各要素をそれより大きい要素に交換する前に.ソートを挿入するコードで、移動要素の距離を1からhに変更するだけです.
これにより、ヒルソートの実装は、ソートを挿入するように、異なるインクリメンタルを使用するプロセスに変換される.
ヒルソートが効率的なのは、配列を部分的にソートし、部分的にソートを挿入するのに適しているためです.
具体コード

fun main(args: Array) {
    val a = arrayOf(1, 32, 2, 23, 5, 234, 12, 978, 2, 2, 0, 4)

    var h=1
    while (h<a.size/3){
        h=3*h+1
    }

    while (h>=1){
        for (i in h until a.size){
            for(j in i downTo h step h){
                if(a[j]>a[j-h]){
                    val t=a[j]
                    a[j]=a[j-h]
                    a[j-h]=t
                }
            }
        }
        h /= 3
    }
    a.forEach { print("$it ") }
}

ヒルソートの詳細な軌跡画像はalgs 4から来ている.cs.princeton.edu
ヒルソートの可視軌跡画像はalgs 4から来ている.cs.princeton.edu
説明
本文の内容は『アルゴリズム』第4版の要約をまとめたものです!