javascriptでquicksort(プログラミングの練習)
|
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 |
function p(a){ console.log(a); } function swap(a, l, r){ var t = a[l]; a[l] = a[r]; a[r] = t; } function getPivot(a, b, c){ if(b < a){ if(a < c){ return a; }else{ return c < b ? c : b; } }else{ if(b < c){ return b; }else{ return c < a ? c : a; } } } function quicksort(a, left, right){ if(left === undefined){ left = 0; } if(right === undefined){ right = a.length - 1; } if(right <= left){ return; } var l = left; var r = right; var p = getPivot(a[l], a[l+1], a[r]); while(true){ while(a[l] < p){ l++; } while(p < a[r]){ r--; } if(r <= l){ break; } swap(a, l, r); l++; r--; } quicksort(a, left, l-1); quicksort(a, r+1, right); } function getRandomIntMinMax(min, max){ min = Number(min); max = Number(max); if(max < min){ return max; } return min + Math.floor(Math.random() * (max - min + 1)); } function getRandomInt(){ var min = 0; var max = 9; return getRandomIntMinMax(min, max); } function dispArrayList(a){ for(var k in a){ var v = a[k]; p(k + " => " + v); } } function setValueFromFuncForArray(a, f){ var len = a.length; for(var i=0; i<len; i++){ a[i] = f(); } } function setRandomForArray(a){ setValueFromFuncForArray(a, getRandomInt); } function resetArray(a){ setValueFromFuncForArray(a, ()=>{return 0;}); } function main(){ var len = 20; var a = Array(len); setRandomForArray(a); p(a); quicksort(a); p(a); } main(); |
|
1 2 |
[ 7, 2, 7, 3, 0, 5, 8, 4, 5, 9, 3, 1, 8, 5, 9, 3, 2, 6, 2, 6 ] [ 0, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 ] |
