퀵 정렬이란?
퀵 정렬이란 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다. JAVA의 Arrays.sort()도 내부적으로 피벗을 하나가 아닌 두 개 사용하여 배열을 세 부분으로 나눈 Dual-Pivot QuickSort를 사용한다.
퀵 정렬은 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇 설정을 무엇으로 하느냐에 따라 효율이 크게 달라진다.
분할 방법은 Hoare(호어), Lomuto(로무토) 방법이 존재하고, Pivot 설정은 랜덤 피봇, 중앙값 피봇, 이중 피봇, 하이브리드 피봇 등 다양한 방식이 있지만 가장 단순한 형태는 인덱스를 배열의 한 부분으로 고정시킨 고정값 피봇이다.(보통 첫 번째 값, 마지막 값, 혹은 가운데 인덱스를 고정)
[이것이 코딩 테스트다 with Python] 23강 퀵 정렬에서 Hoare방식의 퀵 정렬을 쉽게 알 수 있다.
분할 정복(Divide and Conquer)이란?
분할 정복이란 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘을 의미한다. 분할 → 정복 → 결합의 단계로 처리된다.
- 분할 단계에서는 문제를 작은 부분 문제들로 나누는 단계이다.
- 정복 단계에서는 부분 문제를 해결하는 단계이다
- 결합 단계에서는 부분 문제의 해들을 모아 원래의 문제의 해를 구하는 방식을 의미한다.
Hoare(호어) VS Lomuto(로무토)
Pivot 설정
- 랜덤 피봇(Random Pivot): 배열에서 임의의 값을 피벗으로 선택하여 정렬하는 방식.(랜덤 피봇을 사용하면 최악의 경우를 방지할 수 있다.)
- 중앙값 피봇(Median Pivot): 배열의 특정 원소(예: 첫 번째, 마지막, 중간 값 중 중앙값)를 피벗으로 선택하는 방식.
- 이중 피봇(Dual Pivot): 두 개의 피벗을 사용하여 세 개의 부분으로 나누는 방식
- 하이브리드 피봇(Hybrid Pivot): 상황에 따라 다른 피벗 전략을 혼합하여 사용하는 방식
- 고정값 피봇: 배열의 한 부분을 고정시키는 방식
고정된 인덱스 피봇 (가운데 인덱스 고정) vs. 중앙값 피봇
고정된 인덱스 피벗의 가운데 인덱스 선택 방법과 중앙값 피벗 설정 방법의 차이점이 헷갈려 GPT에 물어보았다.
Hoare 분할 방식
- 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.(아래에서 i와 j가 교차했을 때가 이것이 완성된 때)
- 피봇 값을 두 집합의 가운데에 위치시킨다.(아래서 i와 j가 교차했을 때 피봇의 값과 j의 위치와 swap해주는 것)
- 대부분의 강의나 교육자료에서 Hoare 분할 방식을 사용한다.
Lomuto 분할 방식
- 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.
- 피봇 값을 두 집합의 가운데에 위치시킨다.(아래에서 j가 끝까지 진행되었고, i+1와 피폿값이 swap 될 때 이것이 완성된 때)
* Hoare 방식과 가장 큰 차이점은 i와 j가 모두 증가하는 방식이라는 것이다.
퀵 정렬 장점과 단점
| 장점 | 평균적으로 가장 빠른 정렬 알고리즘 중 하나 |
| 추가 메모리 공간이 거의 필요 없음 (인플레이스 정렬) | |
| 캐시 친화적 (Cache-Friendly) | |
| 평균적으로 힙 정렬보다 교환 횟수가 적음 | |
| 단점 | 피벗을 제대로 선택하지 않으면 최악의 경우 O(n²)까지 느려질 수 있음. |
| 안정 정렬이 아님 (Unstable Sort) | |
| 구현이 상대적으로 복잡 | |
| 작은 데이터셋에서는 삽입 정렬보다 느림 |
시간 복잡도
| 알고리즘 | Best | Avg | Worst | Run-time(정수 60,000개) 단위: sec |
| 삽입정렬 | O(n) | O(n²) | O(n²) | 7.438 |
| 선택정렬 | O(n²) | O(n²) | O(n²) | 10.842 |
| 버블정렬 | O(n²) | O(n²) | O(n²) | 22.894 |
| 셸 정렬 | O(n) | O(n¹·⁵) | O(n²) | 0.056 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n²) | 0.014 |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.034 |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.026 |
퀵 정렬 알고리즘 구현
// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)
public void quickSort(int[] arr, int left, int right) {
// base condition
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
// swap(arr, i, sortedIndex);
int tmp = arr[i];
arr[i] = arr[sortedIndex];
arr[sortedIndex] = tmp;
sortedIndex++;
}
}
// swap(arr, sortedIndex, right);
int tmp = arr[sortedIndex];
arr[sortedIndex] = arr[right];
arr[right] = tmp;
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)
import java.util.Arrays;
class GfG {
// Partition function
static int partition(int[] arr, int low, int high) {
// Choose the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;
// Traverse arr[low..high] and move all smaller
// elements to the left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// Move pivot after smaller elements and
// return its position
swap(arr, i + 1, high);
return i + 1;
}
// Swap function
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// The QuickSort function implementation
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// Recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
for (int val : arr) {
System.out.print(val + " ");
}
}
}
//출력
//Sorted Array
//1 5 7 8 9 10참고자료
[1] geeksforgeeks - Quick Sort
[3] 티스토리 Contributor9 - [Java/알고리즘] 정렬 알고리즘(Sort Algorithm) 이해하기 -1 : 기본 구조 및 종류
[4] 데굴데굴 개발자의 기록:티스토리 - [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬
'🧠 Computer Science > Algorithm' 카테고리의 다른 글
| [탐색 알고리즘] 완전 탐색(Exhaustive Search) (0) | 2025.03.28 |
|---|---|
| [정렬 알고리즘] 삽입 정렬(Insertion Sort) (0) | 2024.12.06 |
| [정렬 알고리즘] 선택 정렬(Selection Sort) (0) | 2024.11.30 |
| [정렬 알고리즘] 버블 정렬(Bubble Sort) (1) | 2024.11.29 |
| [그래프 탐색 알고리즘] DFS(깊이 우선 탐색) (0) | 2024.11.21 |
퀵 정렬이란?
퀵 정렬이란 분할 정복(Divide and Conquer) 방법을 사용하여 구현된 정렬 알고리즘을 의미한다. JAVA의 Arrays.sort()도 내부적으로 피벗을 하나가 아닌 두 개 사용하여 배열을 세 부분으로 나눈 Dual-Pivot QuickSort를 사용한다.
퀵 정렬은 분할 알고리즘을 무엇으로 사용하느냐, 그리고 피봇 설정을 무엇으로 하느냐에 따라 효율이 크게 달라진다.
분할 방법은 Hoare(호어), Lomuto(로무토) 방법이 존재하고, Pivot 설정은 랜덤 피봇, 중앙값 피봇, 이중 피봇, 하이브리드 피봇 등 다양한 방식이 있지만 가장 단순한 형태는 인덱스를 배열의 한 부분으로 고정시킨 고정값 피봇이다.(보통 첫 번째 값, 마지막 값, 혹은 가운데 인덱스를 고정)
[이것이 코딩 테스트다 with Python] 23강 퀵 정렬에서 Hoare방식의 퀵 정렬을 쉽게 알 수 있다.
분할 정복(Divide and Conquer)이란?
분할 정복이란 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘을 의미한다. 분할 → 정복 → 결합의 단계로 처리된다.
- 분할 단계에서는 문제를 작은 부분 문제들로 나누는 단계이다.
- 정복 단계에서는 부분 문제를 해결하는 단계이다
- 결합 단계에서는 부분 문제의 해들을 모아 원래의 문제의 해를 구하는 방식을 의미한다.
Hoare(호어) VS Lomuto(로무토)
Pivot 설정
- 랜덤 피봇(Random Pivot): 배열에서 임의의 값을 피벗으로 선택하여 정렬하는 방식.(랜덤 피봇을 사용하면 최악의 경우를 방지할 수 있다.)
- 중앙값 피봇(Median Pivot): 배열의 특정 원소(예: 첫 번째, 마지막, 중간 값 중 중앙값)를 피벗으로 선택하는 방식.
- 이중 피봇(Dual Pivot): 두 개의 피벗을 사용하여 세 개의 부분으로 나누는 방식
- 하이브리드 피봇(Hybrid Pivot): 상황에 따라 다른 피벗 전략을 혼합하여 사용하는 방식
- 고정값 피봇: 배열의 한 부분을 고정시키는 방식
고정된 인덱스 피봇 (가운데 인덱스 고정) vs. 중앙값 피봇
고정된 인덱스 피벗의 가운데 인덱스 선택 방법과 중앙값 피벗 설정 방법의 차이점이 헷갈려 GPT에 물어보았다.
Hoare 분할 방식
- 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.(아래에서 i와 j가 교차했을 때가 이것이 완성된 때)
- 피봇 값을 두 집합의 가운데에 위치시킨다.(아래서 i와 j가 교차했을 때 피봇의 값과 j의 위치와 swap해주는 것)
- 대부분의 강의나 교육자료에서 Hoare 분할 방식을 사용한다.
Lomuto 분할 방식
- 피봇 값보다 큰 값들은 오른쪽, 작은 값들은 왼쪽 집합에 위치시킨다.
- 피봇 값을 두 집합의 가운데에 위치시킨다.(아래에서 j가 끝까지 진행되었고, i+1와 피폿값이 swap 될 때 이것이 완성된 때)
* Hoare 방식과 가장 큰 차이점은 i와 j가 모두 증가하는 방식이라는 것이다.
퀵 정렬 장점과 단점
| 장점 | 평균적으로 가장 빠른 정렬 알고리즘 중 하나 |
| 추가 메모리 공간이 거의 필요 없음 (인플레이스 정렬) | |
| 캐시 친화적 (Cache-Friendly) | |
| 평균적으로 힙 정렬보다 교환 횟수가 적음 | |
| 단점 | 피벗을 제대로 선택하지 않으면 최악의 경우 O(n²)까지 느려질 수 있음. |
| 안정 정렬이 아님 (Unstable Sort) | |
| 구현이 상대적으로 복잡 | |
| 작은 데이터셋에서는 삽입 정렬보다 느림 |
시간 복잡도
| 알고리즘 | Best | Avg | Worst | Run-time(정수 60,000개) 단위: sec |
| 삽입정렬 | O(n) | O(n²) | O(n²) | 7.438 |
| 선택정렬 | O(n²) | O(n²) | O(n²) | 10.842 |
| 버블정렬 | O(n²) | O(n²) | O(n²) | 22.894 |
| 셸 정렬 | O(n) | O(n¹·⁵) | O(n²) | 0.056 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n²) | 0.014 |
| 힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.034 |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | 0.026 |
퀵 정렬 알고리즘 구현
// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)
public void quickSort(int[] arr, int left, int right) {
// base condition
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
// swap(arr, i, sortedIndex);
int tmp = arr[i];
arr[i] = arr[sortedIndex];
arr[sortedIndex] = tmp;
sortedIndex++;
}
}
// swap(arr, sortedIndex, right);
int tmp = arr[sortedIndex];
arr[sortedIndex] = arr[right];
arr[right] = tmp;
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
// 분할 방법: Lomuto(로무토) 분할 방식
// 피벗 설정 방법: 고정된 인덱스 피벗 (마지막 원소 선택)
import java.util.Arrays;
class GfG {
// Partition function
static int partition(int[] arr, int low, int high) {
// Choose the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = low - 1;
// Traverse arr[low..high] and move all smaller
// elements to the left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// Move pivot after smaller elements and
// return its position
swap(arr, i + 1, high);
return i + 1;
}
// Swap function
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// The QuickSort function implementation
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// Recursion calls for smaller elements
// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
for (int val : arr) {
System.out.print(val + " ");
}
}
}
//출력
//Sorted Array
//1 5 7 8 9 10참고자료
[1] geeksforgeeks - Quick Sort
[3] 티스토리 Contributor9 - [Java/알고리즘] 정렬 알고리즘(Sort Algorithm) 이해하기 -1 : 기본 구조 및 종류
[4] 데굴데굴 개발자의 기록:티스토리 - [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬
'🧠 Computer Science > Algorithm' 카테고리의 다른 글
| [탐색 알고리즘] 완전 탐색(Exhaustive Search) (0) | 2025.03.28 |
|---|---|
| [정렬 알고리즘] 삽입 정렬(Insertion Sort) (0) | 2024.12.06 |
| [정렬 알고리즘] 선택 정렬(Selection Sort) (0) | 2024.11.30 |
| [정렬 알고리즘] 버블 정렬(Bubble Sort) (1) | 2024.11.29 |
| [그래프 탐색 알고리즘] DFS(깊이 우선 탐색) (0) | 2024.11.21 |
