ソートのアルゴリズム

Googleの新卒採用向けHangoutをひやかしで見てたら、社員の方がこんな感じのことを言ってた。

Googleの面接といっても難しいことは聞かれなくて、CS(Computer Science)の人なら答えられるであろう質問だった。自分の場合だと、クイックソートを書かされて、そこから性質や計算量のオーダーなどについての説明を求められた

CSやってた人として恥ずかしくない技能を身につけたい!って思いながら毎日過ごしてる自分としては気になるコメント。
ほうほう、クイックソート…。どんなんやったっけ。うろ覚えなまま15分かけて実装するも、あえなく無限ループ。さらに30分かけてバグを取ったのがこちらのコードになります…orz 面接終わってるな。

[cpp]
#include <iostream>
#include <vector>
using namespace std;

void quicksort(const vector<int>::iterator begin, const vector<int>::iterator end) {
if (end – begin <= 1) return;
// pivotには単純に先頭要素を使う
int pivot = *begin;

// 両サイドから走査して、pivot未満の要素とpivot以上の要素の
// 組が見つかったらswap
vector<int>::iterator left = begin, right = end – 1;
do {
while (*left < pivot && left < right) left++;
while (*right >= pivot && left < right) right–;
if (left < right) {
swap(*left, *right);
}
} while (left != right);

// [begin, left)がpivot未満、[left, end)がpivot以上なので、
// leftを境に分割する。ただしleft==beginの時は全要素pivot以上なので
// pivotになった左端の要素は左側の区間に振り分けて区間を小さくする
vector<int>::iterator mid = left;
if (mid == begin) mid++;

// 分割した区間に対して再帰的にsort
quicksort(begin, mid);
quicksort(mid, end);
}

int main() {
static const int a[] = {3, 2, 1, 2, 6, 5, 9, 1, 8};
vector<int> v(sizeof(a) / sizeof(a[0]));
v.assign(a, a + v.size());

quicksort(v.begin(), v.end());

for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << endl;
}

[/cpp]

車輪も1回くらいは作っとくべきだよね。

書いてるうちに気になったのが、STLのsortはどんな実装になってるんだろう?ってこと。検索するとSigmarさんが調べてブログに書いてくれてた。代表的な実装ではこんな感じになっているのだそう。

  1. まずはクイックソート
  2. 再帰がある一定以上深くなったらヒープソートに切り替え
  3. ある程度ソートが進んだら、最後は挿入ソートで仕上げる

手順1と2をまとめてイントロソートっていうらしいです。なるほどなるほどー
汎用的なままよいパフォーマンスを発揮するために工夫されてるんだなぁ

あと、調べてる時に遭遇した、Haskellで書いたクイックソートがかっこよすぎた。
[text]
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
[/text]
Haskellも勉強して嗜んでみたいです。

コメントする