ソートのアルゴリズム

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

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

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

#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;
}

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

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

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

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

あと、調べてる時に遭遇した、Haskellで書いたクイックソートがかっこよすぎた。

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Haskellも勉強して嗜んでみたいです。

コメントを残す

メールアドレスが公開されることはありません。