#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void init(){
srand((unsigned)time(NULL));
}
int getRandomInt_minMax(int min, int max){
if(max<min){
return min;
}
double d = rand() / (double)RAND_MAX;
int randomOffset = (int)(d*(max-min+1));
int reti = min + randomOffset;
return reti;
}
void prti(int arg){
printf("%d\n", arg);
}
void prtf(double arg){
printf("%f\n", arg);
}
void dispArrayList(int* a, int size){
for(int i=0; i<size; i++){
printf("%d => %d\n", i, a[i]);
}
}
void dispArrayLine(int* a, int size){
for(int i=0; i<size; i++){
printf("%2d", a[i]);
if(i!=size-1){
printf(" ");
}else{
printf("\n");
}
}
}
void initArr(int* a, int size){
for(int i=0; i<size; i++){
a[i] = 0;
}
}
void setRandomForArr_minMax(int* a, int size, int min, int max){
for(int i=0; i<size; i++){
a[i] = getRandomInt_minMax(min, max);
}
}
int getPivot(int a, int b, int c){
if(a>b){
if(b>c){
return b;
}else{
return a > c ? c : a;
}
}else{
if(a>c){
return a;
}else{
return b > c ? c : b;
}
}
}
void swap(int* a, int l, int r){
int t = a[l];
a[l] = a[r];
a[r] = t;
}
void quicksort_core(int* a, int size, int left, int right){
if(right<=left){
return;
}
int l = left;
int r = right;
int p = getPivot(a[l], a[l+1], a[r]);
while(1){
while(a[l]<p){
l++;
}
while(p<a[r]){
r--;
}
if(r<=l){
break;
}
swap(a, l, r);
l++;
r--;
}
quicksort_core(a, size, left, l-1);
quicksort_core(a, size, r+1, right);
}
void quicksort(int* a, int size){
quicksort_core(a, size, 0, size-1);
}
int main(void){
// 初期化(乱数の種に時間渡したりとか)
init();
// 変数宣言
int size = 50; // 配列のサイズ
int a[size]; // 整数配列
int min = 0; // 整数乱数の最小値
int max = 99; // 整数乱数の最大値
// 整数配列の各要素に整数乱数をセット
setRandomForArr_minMax(a, size, min, max);
// ソート前出力
dispArrayLine(a, size);
// クイックソート
quicksort(a, size);
// ソート後出力
dispArrayLine(a, size);
}
