JavaScriptでクイックソート
ES6ではデフォルト引数が使えるらしいけれど、
とりあえずデフォルト引数は使わずに実装。
|
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 |
let a = []; let len = 20; for(let i=0; i<len; i++){ a[i] = len-i; } dispArrayLine(a); quicksort(a); dispArrayLine(a); function quicksort(a){ let left = 0; let right = a.length-1; quicksort_core(a,left,right); } function quicksort_core(a, left, right){ if(right<=left){ return; } let l = left; let r = right; let 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 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 swap(a, l, r){ let t = a[l]; a[l] = a[r]; a[r] = t; } function p(arg){ console.log(arg); } function dispArrayList(a){ for(let k in a){ let v = a[k]; p(k + " => " + v); } } function dispArrayLine(a){ let s = ""; for(let k in a){ let v = a[k]; s += v + " "; } s = s.trim(); p(s); } |
