분할 정복(Divide and Conquer) : 문제를 가장 작은 단위로 분리하고 각각 해결 후 결과를 한곳에 모아서 문제를 해결하는 방식
빠른 정렬(Quick Sort)
- 배열에서 기준점을 구한 후 기준점을 기준으로 배열을 나눕니다.(한쪽에는 기준점보다 큰 항목 다른 한쪽은 기준점보다 작은 항목)
- 분할 정복 방법을 통해 배열을 정렬 합니다.
- 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다.
장점
- 초기에 결정된 피벗(기준점)들은 연산에서 제외되고, 피벗을 통해 나눠진 배열의 데이터들의 불필요한 데이터 이동을 줄여서 시간측면에서 굉장히 빠릅니다.
- 배열 안에서 교환하기 때문에 다른 메모리 공간이 필요하지 않습니다.
단점
- 구현하기 어렵습니다.
- 불안정 정렬입니다.
- 정렬된 배열에서는 불균형 분할에 의해 오히려 수행 시간이 더 오래 걸립니다.
CODE
function quickSort(arr) {
return quickSortHelper(arr, 0, arr.length-1)
}
function quickSortHelper(arr, left, right) {
if(left<right) {
var index = partition(arr, left, right)
quickSortHelper(arr, left, index-1);
quickSortHelper(arr, index+1, right)
}
return arr
}
function partition(arr, left, right) {
var pivot = arr[right];
var i = (left-1);
for(var j=left; j<=right-1; j++) {
if(arr[j] <=pivot) {
i++
swap(arr, i, j)
}
}
swap(arr, i+1, right)
return (i+1);
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2]
arr[index2] = temp;
}
console.log(quickSort([1,7,5,2,3,4]))
설명
function quickSort(arr) {
return quickSortHelper(arr, 0, arr.length-1)
}
function quickSortHelper(arr, left, right) {
if(left<right) {
var index = partition(arr, left, right)
console.log('초기 기준점(4)을 기준으로 왼쪽 항목 분할')
quickSortHelper(arr, left, index-1);
console.log("")
console.log('초기 기준점에서 오른쪽 항목 분할')
if(index<right) {
console.log(`초기 기준점 : 4 left : ${index+1}`)
console.log(`left가 초기 기준점 오른쪽에 위치해서 높아서 분할 합니다`)
console.log("")
quickSortHelper(arr, index+1, right)
} else {
console.log(`초기 기준점 : 4 left : ${index}`)
console.log(`left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서 분할하지 않습니다`)
console.log("")
}
}
return arr
}
function partition(arr, left, right) {
console.log('정복 함수 실행')
console.log(arr, `left : ${left}, right : ${right}`)
var pivot = arr[right];
var i = (left-1);
for(var j=left; j<=right-1; j++) {
if(arr[j] <=pivot) {
i++
console.log(`i : ${i}, j : ${j}, ${arr[j]} < ${pivot}`)
swap(arr, i, j)
}
}
console.log("")
console.log(i+1, right)
swap(arr, i+1, right)
return (i+1);
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2]
arr[index2] = temp;
}
console.log(quickSort([1,7,5,2,3,4]))
// 정복 함수 실행
// [ 1, 7, 5, 2, 3, 4 ] left : 0, right : 5
// i : 0, j : 0, 1 < 4
// i : 1, j : 3, 2 < 4
// i : 2, j : 4, 3 < 4
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 0, right : 2
// i : 0, j : 0, 1 < 3
// i : 1, j : 1, 2 < 3
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 0, right : 1
// i : 0, j : 0, 1 < 2
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 1
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서 분할하지 않습니다
//
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 2
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서 분할하지 않습니다
//
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 4
// left가 초기 기준점 오른쪽에 위치해서 높아서 분할 합니다
//
// 정복 함수 실행
// [ 1, 2, 3, 4, 5, 7 ] left : 4, right : 5
// i : 4, j : 4, 5 < 7
//
// 초기 기준점(4)을 기준으로 왼쪽 항목 분할
//
// 초기 기준점에서 오른쪽 항목 분할
// 초기 기준점 : 4 left : 5
// left가 초기 기준점 보다 왼쪽에 있거나 배열의크기 보다 커서 분할하지 않습니다
//
// [ 1, 2, 3, 4, 5, 7 ]