■

クイックソートって、たしかに

ArrayedCollection >> quickSort
  | x xs |
  self isEmpty ifTrue: [^ self].
  x _ self first.
  xs _ self allButFirst.
  ^ (xs select: [: y | y < x]) quickSort, {x}, (xs select: [: y | y >= x]) quickSort

とか

ArrayedCollection >> quickSort
  | x xs suchY |
  self isEmpty ifTrue: [^ self].
  x _ self first.
  xs _ self allButFirst.
  suchY _ [: y | y < x].
  ^ (xs select: suchY) quickSort, {x}, (xs reject: suchY) quickSort

#(63 71 18 9 48 100 61 10 14 57) quickSort
  => #(9 10 14 18 48 57 61 63 71 100)

'pvqsfzwjlygneffzvqmcumbqveqboapn' quickSort
  => 'abbceefffgjlmmnnoppqqqqsuvvvwyzz'

とかいうふうに Smalltalk でも比較的シンプルかつ美しく書けたりするのですが、実は、これだとぜんぜん“クイック”じゃないんですよね。グループ分けのときに新しい配列オブジェクトを生成したりして、そのコストがばかにならない。実際に測定してみると、1000 個のランダムの要素のソートにかかる時間は、Squeak で標準のマージソートに比べて３倍ちょっと。VisualWorks のクイックソートを Squeak に移植したものに比べると６倍以上遅かったりします。すでにソート済み、あるいは降順の配列の処理にいたっては、100倍から200倍と目も当てられない状態。まあ、特殊な事例に対応できないのはアルゴリズムのせいなのでしょうがないとして、せめてランダムなときだけでもマージソートよりは“クイック”にしようと思ったら、どうしても配列を直接書き換えるようなコードにしないといけません（比較対象の VisualWorks 版や Squeak 標準のマージソートがそうなのだから、そうするのが当たり前といえば当たり前ですが…）。VisualWorks のは複雑すぎるので、もうちょっとシンプルにできないかと考えてみたのがこちら。

ArrayedCollection >> quickSort
  ^ self quickSortFrom: 1 to: self size

ArrayedCollection >> quickSortFrom: fromPos to: toPos
  | x cursor last |
  toPos - fromPos < 1 ifTrue: [^ self].
  x _ self at: fromPos.
  cursor _ fromPos.
  last _ toPos + 1.
  [(self at: (last _ last - 1)) > x] whileTrue.
  [cursor < last] whileTrue: [
    (self at: (cursor _ cursor + 1)) > x ifTrue: [
      self swap: cursor with: last.
      [(self at: (last _ last - 1)) > x] whileTrue]].
  self swap: fromPos with: cursor.
  self quickSortFrom: fromPos to: cursor - 1.
  self quickSortFrom: cursor + 1 to: toPos.
  ^ self

これだとランダムな場合なら、VisualWorks 版クイックソートとほぼ互角。グッドです。ただコードは、VisualWorks 版よりはかろうじて短いものの、最初に挙げた一目でなにをしているか分かるコードに比べれば長く難解なのが悩ましいところですね。

こねくりまわしていたら、ひとつ式を付け足すだけで特殊な事例にも対応できることを発見。

ArrayedCollection >> quickSortFrom: fromPos to: toPos
  | middle x cursor last |
  toPos - fromPos < 1 ifTrue: [^ self].
  (self at: (middle _ toPos + fromPos // 2)) > (self at: fromPos)
    ifTrue: [self swap: fromPos with: middle].
  x _ self at: fromPos.
  cursor _ fromPos.
  last _ toPos + 1.
  [(self at: (last _ last - 1)) > x] whileTrue.
  [cursor < last] whileTrue: [
    (self at: (cursor _ cursor + 1)) > x ifTrue: [
      self swap: cursor with: last.
      [(self at: (last _ last - 1)) > x] whileTrue]].
  self swap: fromPos with: cursor.
  self quickSortFrom: fromPos to: cursor - 1.
  self quickSortFrom: cursor + 1 to: toPos.
  ^ self

晴れてコンスタントにクイックに。これはこれでうれしいものです。