sortの使い方

#include 
 
template 
void sort( RandomAccessIterator start, RandomAccessIterator end );
 
template 
void sort( RandomAccessIterator start, RandomAccessIterator end, Compare cmp );

構造体をソートするには、

vector<Type> c;
bool cmp(const Type& a, const Type& b) {
...
}

としてソートすれば良い．

vector, map, set, list(取り消し線はランダムアクセスはできないので、sortは使えない。というかそもそも、set,mapはすでに初期化のときに整理されている。）等は、rbegin(), rend()をもっているので、sortを使って、降順に並び替えることができる．

//vector, map, set
sort(a.rbegin(), a.rend());  //It's smart!!
//list
a.sort();

//こう書くよりも簡単
sort(a.begin(), a.end(), greater<.....>() );
//あるいは、(自分は別にこう書いたことはないが）
sort(a.begin(), a.end());
reverse(a.begin(), a.end());

quicksortの実装

#include 
#include 
using namespace std;

typedef int itemType;

void quicksort(itemType a[], int left, int right) {
  int i, j;
  itemType v;
  if(left < right) {
    v = a[right]; i = left-1; j = right;
    while(1) {
      while(a[++i] < v) ;
      while(a[--j] > v) ;
      if(i >= j) break;
      printf("swap(a[%d], a[%d])\n", i, j);
      swap(a[i], a[j]);
    }
    printf("swap(a[%d], a[%d])\n", i, right);
    swap(a[i], a[right]);
    printf("quicksort(%c, %d, %d);\n", 'a', left, i-1);
    quicksort(a, left, i-1);
    printf("quicksort(%c, %d, %d);\n", 'a', i+1, right);
    quicksort(a, i+1, right);
  }
}


int main() {
  const int N = 9;
  int a[N] = {1, 4, 3, 7, 5, 2, 9, 0, 8};
  quicksort(a, 0, N-1);
  for(int i = 0; i < N; i++) {
    cout << a[i] << endl;
  }
}