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
}
