JavaScript [알고리즘]퀵 정렬(Quick Sort)

<script>

// 교환

function Swap(arr, idx1, idx2) { 

var temp;

temp = arr[idx1];

arr[idx1] = arr[idx2];

arr[idx2] = temp; 

}

 

function Partition(arr, left, right) {

var pivot = arr[left];

low = left + 1;

high = right;

 

while (low <= high) { // 교차되지 않을 때까지 반복

 

// 피벗보다 큰 값을 찾는 과정

while (low <= right  && pivot >= arr[low])

low++;

// 피벗보다 작은 값을 찾는 과정

while (high >= (left+1) && pivot <= arr[high])  

high--;

 

// 교차되지 않는 상태라면 Swap 실행

if (low <= high) { 

Swap(arr, low, high);

}

}

Swap(arr, left, high); // 피벗과 high 가 가리키는 대상 교환

 

return high; // 옮겨진 피벗의 위치정보 교환

}

 

function QuickSort(arr, left, right) {

if (left < right) {

pivot = Partition(arr, left, right); 

QuickSort(arr, left, pivot - 1);

QuickSort(arr, pivot + 1, right);

}

}

 

var arr = [4,2,8,1,9,7,3,6,5];

QuickSort(arr, 0, arr.length - 1);

document.write(arr);

</script>

 

http://terms.naver.com/entry.nhn?docId=2270444&cid=51173&categoryId=51173