자바스크립트 퀵소트 / 퀵정렬

이미지 출처

Github

Worst(최악) - n^2

Best(최선) - n log n

Average(평균) - n log n

위와 같은 시간 복잡도를 가진 정렬 알고리즘입니다.

아래에서 테스트해보실 수 있습니다.

Sort 버튼을 클릭하면 Textarea에 있는 내용을 정렬하고,  Random을 누르면 Textarea의 내용을 0~1000까지 숫자 중 무작위로 100개 집어넣습니다. (중복 가능)

테스트

정렬된 결과가 출력됩니다.

quicksort = (arr, l, r) => {

let i;

(l < r) &&

(

i = partition(arr, l, r),

quicksort(arr, l, i - 1),

quicksort(arr, i + 1, r)

)

return arr

},

partition = (arr, l, r) => {

let i = l,

j = r,

pivot = arr[l];

for (;i < j;)

{

for (;arr[j] > pivot;) j--;

for (;i < j && arr[i] <= pivot;) i++;

tmp = arr[i], arr[i] = arr[j], arr[j] = tmp

}

return arr[l] = arr[j], arr[j] = pivot, j

}

퀵소트 소스입니다.

글을 작성할 당시엔 while보다 for이 퍼포먼스가 좋다고 생각해 for로 짰지만, 확인 결과 그렇지도 않았습니다.

아래는 while을 이용한 코드입니다.

quicksort = (arr, l, r) => {

let i;

(l < r) &&

(

i = partition(arr, l, r),

quicksort(arr, l, i - 1),

quicksort(arr, i + 1, r)

)

return arr

},

partition = (arr, l, r) => {

let i = l,

j = r,

pivot = arr[l];

while (i < j) {

while (arr[j] > pivot) j--;

while (i < j && arr[i] <= pivot) i++;

tmp = arr[i], arr[i] = arr[j], arr[j] = tmp

}

return arr[l] = arr[j], arr[j] = pivot, j

}