クイックソートに最悪ケースを与える。

真ん中の要素をピボットにするクイックソートに非常に計算量が多くなりそうなケースを与えてみた。
クイックソートは
http://www.prefield.com/algorithm/sort/quicksort.html
↑spaghetti source様から拝借しました。

↓は要素数nとソートしたい要素を与えると、クイックソートしてかかった時間を出力してくれるプログラム。

#include<iostream>
#include<vector>
#include<algorithm>
#include<ctime>

using namespace std;


void quicksort(vector<int> &a, int l, int r) {
  if (l < r) {
  	int p = a[(l+r)/2];
    int i = l-1, j = r+1;
    while (1) {
      while (a[++i] < p);
      while (a[--j] > p);
      if (i >= j) break;
      swap(a[i], a[j]);
    }
    quicksort(a, l, i-1);
    quicksort(a, j+1, r);
  }
}
void quicksort(vector<int> &a) {
  quicksort(a, 0, a.size()-1);
}

int main(void){
	 clock_t start, end;
	start = clock();
	int n;
	
	cin >> n;
	
	vector<int>v(n);
	
	for(int i=0;i<n;i++)cin >> v[i];
	quicksort(v);
	
	end = clock();
	cout << end-start <<"[ms]" << endl;
	return 0;
}

↑のプログラムにn/2までの要素を昇順にソートしたものを前半に、降順にソートしたものを後半にしたものを与えた。

↓は要素数nを与えるとそのケースを出力するプログラム。

#include<iostream>

using namespace std;

int main(void){
	
	int n;
	cin >> n;
	cout << n << endl;
	
	for(int i=0;i<n/2;i++)cout << i << " ";
	for(int i=n/2;i<n;i++){
		cout << n-i;
		if(i<n-1)cout << " ";
		else cout << endl;
	}
	
	
return 0;
}

以下のサイト様も参考にしました。
http://www.slideshare.net/kazoo04/quicksort-killer
http://qnighy.hatenablog.com/entry/20090503/1241329233
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf