안녕하세요! 이번 블로그 강좌에서는 자바로 퀵 정렬(Quick Sort) 알고리즘을 구현하는 방법에 대해 알아보겠습니다. 퀵 정렬은 평균 O(n log n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 가지지만, 많은 경우에서 매우 효율적인 정렬 알고리즘으로 알려져 있습니다. 이를 통해 코딩테스트에서의 문제 해결 능력을 향상시킬 수 있습니다.
1. 퀵 정렬이란?
퀵 정렬은 ‘분할 정복’ 방법을 사용하는 정렬 알고리즘입니다. 이 알고리즘은 다음과 같은 과정으로 동작합니다 :
- 정렬할 배열에서 하나의 요소를 ‘피벗(pivot)’으로 선택합니다.
- 배열의 나머지 요소들을 피벗을 기준으로 두 부분으로 나눕니다. 왼쪽 부분은 피벗보다 작은 요소들로, 오른쪽 부분은 피벗보다 큰 요소들로 구성됩니다.
- 왼쪽과 오른쪽 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.
이 과정을 통해 최종적으로 정렬된 배열이 만들어집니다.
2. 문제 정의
문제: 주어진 정수 배열을 퀵 정렬 알고리즘을 통해 정렬하시오.
입력
- 1차원 정수 배열 arr (0 ≤ arr.length ≤ 106, -109 ≤ arr[i] ≤ 109)
출력
- 정렬된 1차원 정수 배열
3. 퀵 정렬 알고리즘 구현
이제 실제로 퀵 정렬 알고리즘을 자바로 구현해보겠습니다. 아래는 퀵 정렬의 자바 코드입니다 :
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // 왼쪽 부분 정렬
quickSort(arr, pi + 1, high); // 오른쪽 부분 정렬
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 피벗값 선택 (구현에서는 마지막 요소)
int i = (low - 1); // 작은 요소의 인덱스
for (int j = low; j < high; j++) {
// 현재 요소가 피벗보다 작으면
if (arr[j] <= pivot) {
i++;
// arr[i]와 arr[j] 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗을 제자리로 이동
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 피벗의 인덱스 반환
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
System.out.println("원본 배열: " + Arrays.toString(arr));
quickSort(arr, 0, n - 1);
System.out.println("정렬된 배열: " + Arrays.toString(arr));
}
}
4. 코드 설명
4.1. 메인 메서드
메인 메서드에서는 정렬할 배열을 정의하고, 원본 배열과 정렬된 배열을 출력합니다. quickSort 메서드를 호출하여 퀵 정렬을 수행합니다.
4.2. quickSort 메서드
quickSort 메서드는 재귀 호출을 통해 배열을 정렬합니다. low와 high는 배열의 인덱스를 나타내며, 기준점인 피벗을 중심으로 배열을 두 부분으로 나눈 후 각 부분에 대해 다시 quickSort를 호출합니다.
4.3. partition 메서드
partition 메서드는 피벗을 기준으로 배열을 나누는 역할을 합니다. 피벗보다 작은 요소는 왼쪽으로 이동하고, 피벗보다 큰 요소는 오른쪽으로 이동합니다. 마지막에 피벗은 제자리로 이동하여 정렬된 배열로 완성됩니다.
5. 시간 복잡도
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 가집니다. 최악의 경우는 이미 정렬되어 있는 배열을 대상으로 피벗을 선택했을 때 발생할 수 있습니다. 하지만 임의의 피벗을 선택하거나 중간값을 선택하는 등 여러 전략을 통해 최악의 경우를 피할 수 있습니다.
6. 결론
이번 글에서는 자바로 퀵 정렬 알고리즘을 구현하는 방법에 대해 알아보았습니다. 퀵 정렬은 매우 유용한 정렬 알고리즘으로, 코딩테스트에서도 자주 출제되므로 꼭 숙지하시기를 권장합니다. 다양한 정렬 알고리즘을 공부하여 문제 해결 능력을 높이는 데 도움이 되기를 바랍니다. 다음 포스트에서는 다른 알고리즘에 대해 다뤄보겠습니다. 읽어주셔서 감사합니다!