C++でクイックソート

クイックソートをC++で実装。
ランダムに0~49の数字を10個作成し、それをソートする。

#include <ctime>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
void quicksort(int *a, int first, int last){
  int f = first;
  int l = last;
  int pivot = a[(f+l)/2];
  while (true){
    while (a[f] < pivot)
      f++;
    while (a[l] > pivot)
      l--;
    if(l <= f)
      break;
    int	tmp = a[f];
    a[f] = a[l];
    a[l] = tmp;
    f++; l--;
  }
  if (first < f-1)
    quicksort(a, first, f-1);
  if(last > l+1)
    quicksort(a, l+1, last);
}
 
void print_array(int *a, int size){   // print array                                                                
  for (int i=0; i<size; i++)
    cout << a[i] << " ";
  cout << endl;
}
 
int main(){
  srand(time(NULL));
  int size = 10;
  int a[size];
  for (int i=0; i<size; i++){ 	// choice between 0 and 49                                                          
    a[i] = rand()%50;
  }
  cout << "before:" << endl;
  print_array(a, size);   // before sorting                                                                            
  quicksort(a, 0, size-1);
  cout << "after:" << endl;
  print_array(a, size);   // after sorting                                                                         
}
 
最終更新:2010年03月06日 00:21
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。