プログラム例

プログラミング言語「つちのこ1.0」のプログラム例です。

クイックソート

クイックソートは、高速なソートアルゴリズムの一種です。次の(1)~(3)の操作を繰り返すことにより、データを並び替えます。
(1)軸となる要素mを決定する(ここでは配列の中央の位置の値とする)
(2)mより大きい値のグループAとmより小さい値のグループBに分ける
(3)グループAとグループBについてそれぞれ再び(1),(2)を適用する
クイックソートは、再帰という構造を用いて実現することができます。次のプログラムは、再帰を用いて書いたクイックソートです。関数「クイックソート」の内部で、軸となる要素より大きい値と小さい値の2つに分けたグループについて、再び「クイックソート」が呼び出されています。
実行
関数 クイックソート(a, start, end):
    m = 切り捨て((start + end) / 2)
    i = start
    j = end
    i < j の間繰り返す:
        a[i] < a[m] の間繰り返す:
            i = i + 1
        a[j] > a[m] の間繰り返す:
            j = j - 1
        もし i < j ならば:
            a[i], a[j] = a[j], a[i]
            もし i == m ならば:
                m = j
            そうでなくもし j == m ならば:
                m = i
            i = i + 1
            j = j - 1
    もし start < i - 1 ならば:
        クイックソート(a,start,m - 1)
    もし end > j + 1 ならば:
        クイックソート(a,m + 1,end)

a = [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
可視化(a)
表示する("ソート前 ",a)
クイックソート(a,0,要素数(a) - 1)
表示する("ソート後 ",a)
クイックソートは、新たにメモリ領域(コピー用の配列など)を用意する必要のない高速なソートアルゴリズムです。配列がバランスよく半分ずつ分割されていけば、個のデータに対して最良でおおよそ回の比較回数で済みますが、データがすでにソート済みである場合や、軸となる要素の選び方によっては、最悪でおおよそ回の比較回数になってしまいます。この欠点を解決するためには、データをあらかじめシャッフルしておくことや、軸となる要素をランダムに決定することが有効です。