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 |
function p(arg){ console.log(arg); } function getRandomInt(min, max){ min = Math.floor(min); max = Math.floor(max); var d = Math.random(); var randomOffset = Math.floor(d * (max - min + 1)); return min + randomOffset; } function dispArrayList(a){ for(var k in a){ var v = a[k]; p(k + " => " + v); } } function dispArrayLine(a, isDispSum){ var sum = 0; var s = ""; for(var k in a){ var v = a[k]; s += v + " "; sum += v; } if(isDispSum){ s += ": " + sum; }else{ s = s.trim(); } console.log(s); } function getArrayInt(size){ var a = []; for(var i=0; i<size; i++){ a[i] = 0; } return a; } function setRandomForArray(a, min, max){ if(undefined === min) min = 0; if(undefined === max) max = 9; for(var i=0; i<a.length; i++){ a[i] = getRandomInt(min, max); } } function swap(a, l, r){ var t = a[l]; a[l] = a[r]; a[r] = t; } function getPivot(a, b, 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; } } } function quicksort(a){ var left = 0; var right = a.length - 1; quicksort_core(a, left, right); } function quicksort_core(a, left, right){ 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_core(a, left, l-1); quicksort_core(a, r+1, right); } function main(){ var size = 20; var a = getArrayInt(size); dispArrayLine(a, true); setRandomForArray(a); dispArrayLine(a, true); quicksort(a); dispArrayLine(a, true); } main(); |
