알고리즘 05 정렬 | 퀵소트 | JS
퀵소트 | Quick sort
- 분할정복을 통해 구현
- 시간복잡도(최악):
O(n^2)
- 시간복잡도(최선):
O(n*logn)
- 분할이 극단적으로 일어나지만 않는다면 대체로
n*logn
으로 수렴
Pivot 값
-
첫번째 값이나 마지막 값을 pivot으로 선택
이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매운 ㅗㅍ음
따라서 좋은 방법이라고 할 수 없음 -
Median of Three
첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 pivot으로 선택
최악의 경우 시간복잡도가 달라지지 않음 -
Randomized quickSort
pivot을 랜덤하게 선택
no worst case instance, but worst case execution
평균 시간복잡도 O(NlogN)
구현
// 본인 구현
// 마지막 요소를 pivot으로 두고 앞의 값들과 비교
// pivot값보다 작은 경우와 큰 경우로 나누어 좌측, 우측으로 몰아넣음
// i+1값과 pivot 값을 swap
// 위의 gif 이미지와 동일하게 작업을 수행
unction quickSort(arr) {
if (arr.length <= 1) return arr
let i = -1;
let j = 0;
let pivot = arr[arr.length - 1]
let temp = null
while (j < arr.length) {
if (arr[j] < pivot || j === arr.length - 1) {
temp = arr[i + 1]
arr[i + 1] = arr[j]
arr[j] = temp
i++
}
j++
}
return [...quickSort(arr.slice(0, i)), arr[i], ...quickSort(arr.slice(i + 1))]
}
const arr = [31, 8, 48, 8, 73, 11, 3, 20, 8, 29, 65, 15]
console.log(quickSort(arr));
// zerocho 구현
var partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
var temp;
var pivot = array[pivotIndex];
while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어갑니다.
while (array[left] < pivot)
left++;
while (array[right] > pivot)
right--;
if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
temp = array[left];
array[left] = array[right];
array[right] = temp; // 서로 바꿔줍니다.
left++;
right--;
}
}
temp = array[left];
array[left] = array[pivotIndex];
array[pivotIndex] = temp; // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 i입니다.
return left;
};
var quickSort = function(array, left, right) { // 재귀하는 부분
if (!left) left = 0;
if (!right) right = array.length - 1;
var pivotIndex = right; // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.
pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.
if (left < pivotIndex - 1)
quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
if (pivotIndex + 1 < right)
quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
return array;
};
quickSort([4,1,7,6,3,8,2,5]); // [1,2,3,4,5,6,7,8]
📚 참고
YOUTUBE | 2015 봄학기 알고리즘 | 권오흠
퀵 정렬(quick sort) by.zerocho
Photo by Michael Dziedzic on Unsplash
Author And Source
이 문제에 관하여(알고리즘 05 정렬 | 퀵소트 | JS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/알고리즘-05-정렬-퀵-정렬-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)