퀵 정렬!
우선 퀵 정렬은 분할 정복 알고리즘을 사용하고 있다.
절차에 대해서 간략하게 설명하자면
우선 기준이 될 값을 정해준다.(0번 인덱스)
그 후, 좌측에서부터 돌아가며 기준 값보다 큰 요소를 결정하고, 오른쪽 끝에서부터 돌아가며 기준 값보다 작은 요소를 결정한다. 그 후 그 요소들의 위치를 서로 바꾸어준다.
이 작업을 반복하면서 큰 값과 작은 값의 인덱스 번호가 교차한다면 작은 값의 위치와 기준 값의 위치를 바꾸어준다.
그 후 중앙쪽으로 이동한 기준 값의 위치를 두고 좌 우로 나누어서 다시 작업을 반복한다.
(전개되는 방식이 언뜻 봤던 이진검색트리와 비슷한 느낌을 받았다.)
일단은 이런 설명을 듣고 알고리즘을 짜보았다.
function quick(arr) {
let eindex1;
let eindex2;
let num;
for (let i = 0; i < arr.length; i++) {
if (arr[0] < arr[i]) {
eindex1 = i;
break;
}
}
for (let j = arr.length - 1; j >= 0; j--) {
if (arr[0] > arr[j]) {
eindex2 = j;
break;
}
}
if (eindex1 - eindex2 == 1 || eindex1 == 0) {
num = arr[eindex2];
arr[eindex2] = arr[0];
arr[0] = num;
let arrL = quickLeft(arr, eindex2);
let arrR = quickRight(arr, eindex2);
return console.log(arrL, arrR);
} else {
num = arr[eindex1];
arr[eindex1] = arr[eindex2];
arr[eindex2] = num;
}
return quick(arr);
}
function quickLeft(arr, eindex2) {
let arrL = [];
for (let i = 0; i < eindex2; i++) {
arrL.push(arr[i]);
}
return arrL;
}
function quickRight(arr, eindex2) {
let arrR = [];
for (let i = eindex2 + 1; i < arr.length; i++) {
arrR.push(arr[i]);
}
return arrR;
}음.. 정말 설명대로 조건에 부합하는 요소를 저장해두었다가... 다시 비교해서 옮기고... 순환 한 번이 끝나면 다시 반복시켜서 교차하는 순간에 quickLeft && quickRight라는 함수를 만들어서 기준값 중심의 왼쪽과 오른쪽 배열을 만들고...
이런식으로 구성을 하니 너무 번잡스럽고 재귀함수의 형식으로 돌렸으나 빠져나오는 예외처리나 좌우로 배열이 쪼개졌을 때 쪼개진 배열을 어떻게 돌릴지 막막해졌다...
그래서 방법을 찾아보았더니 기준값으로 큰 수인지 작은 수인지 비교를 하기 위해 따로 저장하거나 하는 것이 아니라
빈 배열 두 개를 미리 만들어 놓고 push하는 방식을 사용하는 것이 눈에 띄었다.
function qSort(arr) {
if (arr.length === 0) {
return [];
}
let l = arr.length;
let center = arr[0];
let left = [];
let right = [];
for (let i = 1; i < l; i++) {
if (center > arr[i]) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...qSort(left), center, ...qSort(right)];
}알고리즘 진행 방식 자체는 기준 값보다 크고, 작은 수를 정해서 둘을 바꾸는 과정과 그 후에 기준 값을 기준으로 좌측 우측을 쪼개는 과정이 서술되어있었고 그걸 구현해보는 과정에서 코드가 복잡하게 꼬였었는데
left, right 배열을 선언해서 push하는 것으로 해당 과정을 함축할 수 있었다...
그리고 재귀함수 형식으로 return에서 left와 right를 다시 qSort함수에 넣어줌으로써 조건에 맞을 때까지 반복시켜주었다.
퀵정렬은 평균적인 속도(n*log n)가 매우 빠른 정렬이라고 한다.
다만 조금 독특한 단점이 있었는데
정렬되어져있는 배열을 돌렸을 경우 오히려 섞여있는 상황보다 시간이 더 오래걸리는 것이다.
가장 최선의 경우는 첫 기준점으로 잡힌 값이 배열의 중앙값일 때,
좌, 우측으로 나누어지는 배열의 길이가 균등하여 가장 이상적인 상황이고
배열이 정렬되어져있을 경우, 좌, 우측으로 나누어지는 상황에서 한 쪽으로 쏠리기에 오히려 끝까지 돌아야하는 상황이 발생하여 시간이 더 오래 걸리게 된다.(n^2)
평균적으로 보았을 때는 삽입정렬보다 훨씬 빠르지만 특정한 경우에서는 오히려 못하는 상황도 발생하는 것이다.
결국 가장 좋은 정렬이 무엇인가에 대한 답은 없고, 어떠한 상황에서 어떠한 정렬을 써야하는지에 대한 답만 존재하는 것 같다.
