Quick Sort 구현
문제
평균적인 시나리오에서 시간복잡도가 낮기로 알려진 Quick Sort
를 자바스크립트로 구현해본다.
예시
arr | result |
---|---|
[0, 5, 2, 1, 6, 3] | [0,1,2,3,5,6] |
[3, 6, 0, 2, 4, 1, 7, 5] | [0,1,2,3,4,5,6,7] |
풀이 (분할)
- 퀵 정렬은
분할
이라는 개념에 기반한다. - 분할을 통해 배열에서 임의의 수를 가져와(여기서는 배열의 맨 오른쪽 수)
피벗
으로 정하고, 피벗에서 작은 모든 수는 피벗의 왼쪽에, 큰 수는 피벗의 오른쪽에 둔다. - 두 개의
포인터
를 두는데, 왼쪽 포인터는 배열의0
번째 인덱스에서부터, 오른쪽 포인터는피벗의 한 칸 앞
인덱스에서부터 시작한다. - 왼쪽 포인터가 가리키는 값이 피벗이 가리키는 값보다 크거나 같아질 때 까지 포인터를 계속 한 칸 씩 이동한다.
- 왼쪽 포인터의 이동이 끝나면, 오른쪽 포인터의 이동을 시작하는데, 오른쪽 포인터는 피벗이 가리키는 값보다 작거나 같아질 때까지 포인터를 계속 한 칸 씩 이동한다.
- 두 포인터의 이동이 끝나면, 두 포인터가 배열 내에서 만났는지 검사하고, 만났다면 왼쪽 포인터와 피벗을 바꾸고, 왼쪽 포인터를 반환하고 함수를 끝낸다. 그렇지 않다면 두 포인터의 위치를 바꾸고 4~6번 풀이를 반복한다.
- 위 과정을 끝내면 피벗의 왼쪽에는 피벗보다 같거나 작은 숫자들만 모여있게 된다.
풀이 (퀵 정렬)
- 분할에서 반환한 왼쪽 포인터를 피벗으로 두고, 피벗을 기준으로 왼쪽의 남은 원소들로 서브 배열을 만들어서 퀵 정렬 함수를 재귀로 실행시키고, 오른쪽 원소들로도 동일한 작업을 한다.
- 위 분할에서 배열 내 원소의 개수가 1개 또는 0개일 때는 아무런 일도 일어나지 않으므로, 퀵 정렬 함수의 기저 조건을 퀵 정렬이 적용되는 원소의 개수가 1개 또는 0개일 때로 지정한다.
코드
class Sort {
constructor(arr) {
this.arr = arr;
}
partition (lPointer, rPointer){
let pivot = rPointer;
let pivotNum = this.arr[pivot];
rPointer--;
while (true) {
while (this.arr[lPointer] < pivotNum) {
lPointer++;
}
while (this.arr[rPointer] > pivotNum) {
rPointer--;
}
if (lPointer >= rPointer) break;
else this.swap(lPointer, rPointer);
}
this.swap(lPointer, pivot);
return lPointer;
}
swap (lPointer, rPointer) {
let tempValue = 0;
tempValue = this.arr[lPointer];
this.arr[lPointer] = this.arr[rPointer];
this.arr[rPointer] = tempValue;
}
quickSort (lIndex, rIndex) {
if(rIndex - lIndex <= 0) return;
const pivotPosition = this.partition(lIndex, rIndex);
this.quickSort(lIndex, pivotPosition-1);
this.quickSort(pivotPosition+1, rIndex);
return this.arr;
}
}
const arr1 = [0, 5, 2, 1, 6, 3];
const sortableArr = new Sort(arr1);
sortableArr.quickSort(0, arr1.length-1);
REFERENCE
누구나 자료 구조와 알고리즘 - 제이 웬그로우
Author And Source
이 문제에 관하여(Quick Sort 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/Quick-Sort-구현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)