코딩테스트에서 자주 등장하는 문제 중 하나가 배열 정렬입니다. 이 강좌에서는 퀵 정렬(Quick Sort) 알고리즘에 대해 알아보고, 이를 자바스크립트로 구현하는 방법을 자세히 설명하겠습니다. 퀵 정렬은 효율적인 정렬 알고리즘으로, 분할 정복(Divide and Conquer) 기법을 이용합니다.
문제 설명
주어진 배열을 퀵 정렬 알고리즘을 사용하여 오름차순으로 정렬하시오.
예제 입력: [34, 7, 23, 32, 5, 62]
예제 출력: [5, 7, 23, 32, 34, 62]퀵 정렬 알고리즘 개요
퀵 정렬은 아래와 같은 단계로 진행됩니다.
- 배열에서 하나의 원소를 피벗(pivot)으로 선택합니다.
- 피벗을 기준으로 배열을 두 개의 부분 배열로 나눕니다. 하나는 피벗보다 작은 원소들로 구성되고, 다른 하나는 피벗보다 큰 원소들로 구성됩니다.
- 각 부분 배열에 대해 동일한 방법을 재귀적으로 적용합니다.
- 부분 배열이 크기가 0 또는 1이 될 때까지 반복합니다.
예제 설명
입력 배열이 [34, 7, 23, 32, 5, 62]일 경우, 다음과 같은 과정을 거칩니다.
- 피벗 선택: 배열의 마지막 원소인 62를 피벗으로 선택합니다.
- 분할: 피벗인 62보다 작은 원소들([34, 7, 23, 32, 5])과 큰 원소([])로 배열을 나눕니다.
- 재귀 호출: 피벗보다 작은 부분 배열 [34, 7, 23, 32, 5]에 대해 동일한 과정을 반복합니다.
- 이 과정을 반복하여 최종적으로 배열이 정렬됩니다.
자바스크립트 구현
이제 퀵 정렬 알고리즘을 자바스크립트로 구현해 보겠습니다.
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // 크기가 0 또는 1인 경우 그대로 반환
}
const pivot = arr[arr.length - 1]; // 피벗으로 마지막 원소 선택
const left = []; // 피벗보다 작은 원소를 저장할 배열
const right = []; // 피벗보다 큰 원소를 저장할 배열
// 배열을 순회하며 피벗과 비교
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 재귀 호출 및 결과 배열 반환
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 예제 배열
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = quickSort(array);
console.log(sortedArray); // [5, 7, 23, 32, 34, 62]알고리즘의 시간 복잡도
퀵 정렬 알고리즘의 평균적인 시간 복잡도는 O(n log n)입니다. 하지만 최악의 경우에는 O(n²)의 시간 복잡도를 가질 수 있습니다. 이는 피벗 선택이 불균형할 경우 발생할 수 있습니다. 이 때문에 퀵 정렬은 피벗을 무작위로 선택하는 등의 최적화 기법을 통해 성능을 향상시킬 수 있습니다.
퀵 정렬의 장단점
장점
- 효율적인 정렬 알고리즘으로, 대규모 데이터 정렬에 적합합니다.
- 메모리 사용량이 적어, 인플레이스(in-place) 정렬이 가능합니다.
단점
- 최악의 경우 시간 복잡도가 O(n²)로 비효율적입니다.
- 재귀적으로 호출되므로 스택 메모리 사용이 발생합니다.
결론
이번 강좌에서는 퀵 정렬 알고리즘과 함께, 이를 자바스크립트로 구현하는 방법에 대해 배워보았습니다. 퀵 정렬은 구현이 간단하고 효율적인 정렬 알고리즘으로, 코딩테스트와 알고리즘 문제 풀이에 자주 사용됩니다. 학습한 내용을 바탕으로 다양한 배열 정렬 문제를 풀어보시기 바랍니다.
다음 강좌에서는 다른 정렬 알고리즘인 머지 정렬(Merge Sort)에 대해 다룰 예정입니다. 관심을 가져 주시기 바랍니다!