クイックソートと最悪ケース

はじめに

とりあえずクイックソートを書いてみた

昨晩、思い立ってクイックソートを書いてみようとしたら動きませんでした(白目)
その時書いたコードが以下。

#include<iostream>
#include<fstream>
const int MAX_N = 1000000;
int a[MAX_N];

void Qsort(int,int);//ソートするとこ
int Median(int,int,int);//3つの引数から中央値を取る
void Qsort(int left, int right){
  int i = left;
  int j = right;
  int pivot = Median(a[i],a[j],a[(i+j)/2]);
  while(i < j){
    while(a[i] < pivot)i++;
    while(a[j] > pivot)j--;
    std::swap(a[i],a[j]);
    i++;
    j--;
  }
  if(left < j)
    Qsort(left, j);
  if(i < right)
    Qsort(i, right);
}

int Median(int a, int b, int c){
  using namespace std;
  return max( max(min(a,b), min(b,c)), min(c,a));
}

int main(){
  std::fstream file;
  file.open("sorted.t", std::ios::out);
  if(!file.is_open()){
    std::cout <<"cannot open file."<<std::endl;
    return -1;
  }

  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::cin >> a[i];
  }

  Qsort(0,n-1);
  
　//ソートした結果をファイルに出力。一行目は要素数
  file << n << std::endl;
  for(int i = 0; i < n; i++){
    file << a[i] << std::endl;
  }
  file.close();
  std::cout << "sorted.t is generated." << std::endl;
}

クイックソートは3つくらい値を持ってきて中央値をピボットに取るといいよ、というのをどっかでみたのでこういう感じです。
要素数が多いとさすがにコンソールに出力してられないよな、ということでソート後の配列をファイルに出力してます。
>でリダイレクトすれば解決するけどもまあファイルを使う練習的な意味も込めて。
.tという拡張子に意味は無いですが、一応なんかつけとこうと思ってつけました。

さて、こんな感じでクイックソートを書いたわけですが、うまく動作しません！
なぜだろうと頭をひねりまくっても深夜だったので潔く諦め、グーグル大先生の教えを乞いました。
悪さをしていたのはもちろんQsortの部分です。
以下のように変更すると、動きました。

void Qsort(int left, int right){
  int i = left;
  int j = right;
  int pivot = Median(a[i], a[j], a[(i+j)/2]);
  while(true){//while(i <= j) => while(true)
    while(a[i] < pivot)i++;
    while(a[j] > pivot)j--;
    if(i >= j) break;//追加
    std::swap(a[i],a[j]);
    i++;
    j--;
  }

  if(left < i-1)//if(left < j) => if(left < i-1)
    Qsort(left, i-1);//j=>i-1
  if(j+1 < right)//if(i < right) => if(j+1 < right)
    Qsort(j+1, right);//i=>j+1
}

これで動きました。
なぜ変更前はうまく動作しなかったのか、なぜ変更後は正しく動作するようになったのかというと、
よく分かっておりません(´・ω・`)
紙に図を書いてトレースしていけばなんとかなりそうなのでそのうちなんとかします。

クイックソート速いよクイックソート

クイックソート、速いです。普通に動けばめちゃくちゃ速いです。
どれくらい速いかって言うと、単純なソートだと30分以上ソートにかかるような場合でも、1秒以内でソートが完了するくらい速いです。
適当にソートの処理を書いて、比較してみた。出力部分は時間がかかるので削除。
データ数が多いと入力にも結構時間がかかってくるので、それも考える必要があります。

//普通のソート
#include<iostream>
const int MAX_N = 1000000;
int a[MAX_N];

void Sort(int n){
  for(int i = 0; i < n-1; i++){
    for(int j = i+1; j < n; j++){
      if(a[i] > a[j])
	std::swap(a[i],a[j]);
    }
  }
}
int main(){
  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::cin >> a[i];
  }
  Sort(n);		      
  std::cout << "Fin." << std::endl;
}

//クイックソート
#include<iostream>
const int MAX_N = 1000000;
int a[MAX_N];

void Qsort(int,int);
int Median(int,int,int);

void Qsort(int left, int right){
  int i = left;
  int j = right;
  int pivot = Median(a[i], a[j], a[(i+j)/2]);
  while(true){
    while(a[i] < pivot){
      i++;
    }
    while(a[j] > pivot){
      j--;
    }
    if(i >= j) break;
    std::swap(a[i],a[j]);
    i++;
    j--;
  }

  if(left < i-1){
    Qsort(left, i-1);
  }
  if(j+1 < right){
    Qsort(j+1, right);
  }
}

int Median(int a, int b, int c){
  using namespace std;
  return max( max(min(a,b), min(b,c)), min(c,a));
}

int main(){
  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::cin >> a[i];
  }

  Qsort(0,n-1);
  std::cout <<"Fin."<<std::endl;
}

それぞれ5回行った平均値をとってます。入力データは毎回ランダムに変更しました。
時間はtimeコマンドのuserの値を使用しています。
N=1000(10^3)

	普通のソート	クイックソート	入力にかかった時間
user	0.008s	0.000s	0.000s
実質かかった時間	0.008s	0.000s	/

N=10000(10^4)

	普通のソート	クイックソート	入力にかかった時間
user	0.630s	0.008s	0.0056s
実質かかった時間	0.624s	0.002s	/

N=100000(10^5)

	普通のソート	クイックソート	入力にかかった時間
user	62.293s	0.104s	0.078s
実質かかった時間	62.215s	0.026s	/

N=1000000(10^6)

	普通のソート	クイックソート	入力にかかった時間
user	計測無理	1.146s	0.824s
実質かかった時間	約1時間	0.322s	/

どうです？速いでしょう？
N=10^6で普通のソートだと死んでるところでも、クイックソートなら余裕です。
あと1つゼロが増えても10秒ちょっとで終わりそうですね。
O(N^2)とO(NlogN)の違いってすごいなと改めて実感できます。
が、最悪ケースだとクイックソートでもO(N^2)になってしまうので実験しました。

最悪ケースとは

クイックソートで、ピボットの値を分割した範囲の左端値(a[left])または右端値(a[right])にしたとき、すでに整列済みのデータを入力すると、次の範囲の分割がうまいこといかないので非常に効率が悪くなります。
詳しいことは検索すると出てくるのでそちらに任せるとして、
最悪ケースだとどんぐらい悪くなるのよ？っていうことを試したよ。
今回書いたコードだと、ピボットはa[left],a[right],a[(left+right)/2]の中央値を取るので、整列済みデータを与えても速いです。
ので、ピボットのとこをpivot=a[left]に書き換えて実行したものと比較です。
N=10000

	改良	最悪	普通のソート	入力にかかった時間
user	0.006s	0.168s	0.0216s	0.006s
ソートにかかった時間	0.000s	0.162s	0.210s	/

N=100000

	改良	最悪	普通のソート	入力にかかった時間
user	0.086s	16.616s	20.165s	0.072s
ソートにかかった時間	0.012s	16.444s	20.093s	/

N=1000000

	改良	最悪	普通のソート	入力にかかった時間
user	0.973s	計測断念	計測断念	0.840s
ソートにかかった時間	0.133s	約1600秒？	約2000秒？	/

最悪ケースにひっかかると、クイックソートでもこんなに遅くなります。
マジ遅いです。ありえないです。
普段なら高速に処理できるのに、特殊なケースな場合はとんでもなく遅くなってしまう、みたいなことがあるんですね。(他人事)