クイックソートを
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