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 |
#include <stdio.h> #include <stdlib.h> void init(){ srand((unsigned)time(NULL)); } double getRandomDouble(){ return (rand() * 1.0) / RAND_MAX; } int getRandomInt(int min, int max){ if(max <= min){ return max; } int pad = (int)(getRandomDouble() * (max - min + 1)); return min + pad; } void resetArray(int a[], int size){ for(int i=0; i<size; i++){ a[i] = 0; } } 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("%d", a[i]); if(i<size-1){ printf(" "); }else{ printf("\n"); } } } void setRandomIntForArray(int a[], int size, int min, int max){ for(int i=0; i<size; i++){ a[i] = getRandomInt(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){ int left = 0; int right = size-1; quicksort_core(a, size, left, right); } int main(){ init(); int size = 20; int a[size]; resetArray(a, size); dispArrayLine(a, size); setRandomIntForArray(a, size, 0, 9); dispArrayLine(a, size); quicksort(a,size); dispArrayLine(a, size); } |
