クイックソート(C言語)
クイックソートquicksortのアルゴリズムは難しいから暗記している。
ユズノハは3年半C言語で働いていたが、会社を辞めてからはJavaやらPHPばかり書いており、
そういえばC言語でクイックソートを書いたことがなかったなと思い書いてみた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#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); } |
見ての通りquicksort_core()は再帰呼出し。
C言語は関数のオーバーロード(多重定義)ができないため、quicksort()とquicksort_core()の2つが必要になる。
更に配列のサイズも配列変数から取得できないため引数で渡す必要がある。
メイン関数が一番下なのはサブ関数のプロトタイプ宣言を省略するため。
やはりC言語は不便な言語だ。
ハードウェアに近いところをいじる時以外はC言語は遠慮したい。
