shakerSort

構文
shakerSort( Var array )
引数
array
ソートする数値を格納した配列。参照引数。
戻値

プログラム

////////////////////////////////////////////////// // 【引数】 // array : ソートする数値を格納した配列。参照引数。 // 【戻値】 // ////////////////////////////////////////////////// PROCEDURE shakerSort(Var array[]) DIM topIndex = 0 DIM bottomIndex = UBound(array) - 1 WHILE TRUE DIM lastSwapIndex = topIndex FOR n = topIndex TO bottomIndex IFB array[n] > array[n+1] THEN swap(array[n], array[n+1]) lastSwapIndex = n ENDIF NEXT bottomIndex = lastSwapIndex IF topIndex = bottomIndex THEN BREAK FOR n = bottomIndex TO topIndex + 1 STEP -1 IFB array[n] < array[n-1] THEN swap(array[n], array[n-1]) lastSwapIndex = n ENDIF NEXT topIndex = lastSwapIndex IF topIndex = bottomIndex THEN BREAK WEND FEND ////////////////////////////////////////////////// // 【引数】 // a : 変数bと交換する値。参照引数。 // b : 変数aと交換する値。参照引数。 // 【戻値】 // ////////////////////////////////////////////////// PROCEDURE swap(Var a, Var b) DIM tmp = a a = b b = tmp FEND ////////////////////////////////////////////////// // 【引数】 // 配列 : 上限値を求める配列 // 【戻値】 // 配列の上限値 ////////////////////////////////////////////////// FUNCTION UBound(array[]) RESULT = RESIZE(array) FEND

解説

  1. 2-3行目
    DIM topIndex = 0 DIM bottomIndex = UBound(array) - 1
    topIndex
    bottomIndex
  2. 4-22行目
    WHILE TRUE DIM lastSwapIndex = topIndex FOR n = topIndex TO bottomIndex IFB array[n] > array[n+1] THEN swap(array[n], array[n+1]) lastSwapIndex = n ENDIF NEXT bottomIndex = lastSwapIndex IF topIndex = bottomIndex THEN BREAK FOR n = bottomIndex TO topIndex + 1 STEP -1 IFB array[n] < array[n-1] THEN swap(array[n], array[n-1]) lastSwapIndex = n ENDIF NEXT topIndex = lastSwapIndex IF topIndex = bottomIndex THEN BREAK WEND
    lastSwapIndex
    最後に要素を入れ替えた位置。

シェーカーソート

シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良もの。した双方向バブルソート、改良交換法とも言われます。

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行います。

アルゴリズム

バブルソートで1回スキャンを行うと最後の要素1個がスキャン範囲中最大であることがわかり、次回のスキャン範囲を1狭めることができます。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができます。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになります。