안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입, 병합)
불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택,퀵)
📌퀵 정렬
퀵 정렬은 특정한 값을 기준으로 해당 값보다 큰 숫자와 작은 숫자를 서로 교환하면서 정렬을 수행합니다.
퀵 정렬은 대표적인 분할 정복 알고리즘으로 평균적으로 선택 정렬, 버블 정렬, 삽입 정렬보다 월등히 빠르다는 특징을 가지고 있습니다.
위 세가지 정렬이 O(N2)인것에 비해 퀵 정렬은 O(N*logN)의 속도를 가지고 있기 때문입니다.
비교의 기준이 되는 특정한 값을 피봇(Pivot)이라고 부르며 보통 가장 앞에 있는 숫자를 Pivot으로 사용합니다.
작동 원리
- 배열을 왼쪽에서 오른쪽으로 순회하면서 Pivot 보다 큰 수를 찾습니다.
- 배열을 오른쪽에서 왼쪽으로 순회하면서 Pivot보다 작은 수를 찾습니다.
- 1의 결과와 2의 결과를 서로 Swap합니다.
단, 2의 결과가 1의 결과보다 더 왼쪽에 있을 경우 Pivot과 2의 결과(작은 수)를 서로 Swap합니다.
이때, Pivot의 왼쪽은 Pivot보다 작고, 오른쪽은 Pivot보다 큽니다.
시간 복잡도
퀵 정렬은 O(N*logN)의 시간 복잡도를 가집니다. 이게 O(N2)보다 얼마나 빠른지 감이 잘 안잡히시죠?
N이 1,000,000이라면?(정확한 차이는 아닙니다. 대략적으로 이해만 해주세요.)
- O(N2) : 1,000,000 * 1,000,000 = 1,000,000,000,000(1조)
- O(N*logN) : 1,000,000 * 약 20(log21,000,000) = 20,000,000(2천만)
둘은 약 50,000배의 속도 차이를 보여줍니다.
이렇듯 퀵 정렬은 월등히 빠른 속도를 자랑합니다. 그러나 항상 O(N*logN)을 보장해주지는 않습니다.
1,2,3,4,5,6,7,8,9,10을 퀵 정렬로 정렬할 경우 10+9+8+..+1번 배열에 접근하므로 O(N2)의 시간 복잡도를 가집니다.
이를 삽입 정렬로 정렬할 경우 O(N)만에 정렬이 완료되게 됩니다.
이렇듯 ‘어떠한 방법이 가장 좋다.’ 라고 확정지을 순 없으며 정렬하고자하는 대상에 따라 적절한 방법을 선택하는 것이 매우 중요합니다.
예시를 통해 알아봅시다.
쉬운 이해를 위해서 다음과 같이 1부터 7까지 총 7개의 숫자가 들어있는 배열을 기준으로 설명하겠습니다.
[6, 5, 1, 4, 7, 2, 3]
항상 정 가운데를 기준으로 분할을 하는 병합 정렬과 달리, 퀵 정렬은 흔히 피봇(pivot)이라고 불리는 임의의 기준값을 사용합니다. pivot 값을 선택하는데는 여러가지 방법이 있지만 여기서는 간단한 설명을 위해 정 중앙에 위치한 4을 pivot으로 정하겠습니다. 그리고 다음과 같이 이 pivot 값을 기준으로 pivot보다 작은 값의 그룹과 pivot보다 큰 값의 그룹으로 나눕니다.
p
[3, 2, 1] < 4 < [7, 5, 6]
위와 같이 pivot 값보다 작은 값들은 모두 왼편으로 몰고, 큰 값들은 모두 오른편으로 몰면 기준값은 정확히 정렬된 위치에 놓이게 됩니다.
또한 이런 방식으로 분할을 해놓으면 앞으로 더 이상 왼편에 있는 값들과 오른편에 있는 값들 간에는 비교를 할 필요가 없습니다.
따라서 반대편은 전혀 신경쓰지 않고 왼편이든 오른편이든 같은편 내의 값들 끼리만 비교 후 정렬을 할 수 있게 됩니다.
먼저 왼편을 동일한 방식으로 정렬해보도록 하겠습니다. 왼편의 정 가운데에 위치한 pivot 값인 2 보다 작은 값인 1인 왼쪽에 큰 값인 3은 오른쪽에 위치시켰습니다. 이제 양쪽 모두 값이 하나씩 밖에 없기 때문에 이로써 왼편의 정렬 작업은 완료되었습니다.
p
[1] < 2 < [3]
오른편도 동일한 방식으로 정렬해보겠습니다. 오른편의 pivot 값인 5 보다 작은 값은 없으므로 7과 6을 모두 오른편에 위치시켰습니다.
p
[] < 5 < [7, 6]
오른편의 오른편(?)에는 값이 2개가 있기 때문에 추가 정렬이 필요합니다. 왼편에는 값이 없지만 오른편에는 여전히 두 개의 값이 있기 때문에, 동일한 방식의 정렬을 적용하겠습니다.
p
[6] < 7 < []
마지막으로 지금까지 좌우로 분할했던 값들을 모두 합치보면 다음과 같이 정렬된 배열을 얻을 수 있습니다.
[1, 2, 3, 4, 5, 6, 7]
지금까지 살펴본 것과 같이 퀵 정렬은 배열을 pivot 값 기준으로 더 작은 값과 큰 값으로 반복적으로 분할하여 정렬해나가는 방식을 취하고 있습니다.
구현
먼저 리스트의 정 가운데 있는 값을 pivot 값으로 선택하고, pivot 값보다 작은 값, 동일한 값 그리고 큰 값을 담아둘 3개의 리스트를 생성합니다.
그리고 반복문을 통해 각 값을 pivot과 비교 후에 해당하는 리스트에 추가시킵니다.
그 다음 작은 값과 큰 값을 담고 있는 배열을 대상으로 퀵 정렬 함수를 재귀적으로 호출합니다.
마지막으로 재귀 호출의 결과를 다시 크기 순으로 합치면 정렬된 리스트를 얻을 수 있습니다.
import java.util.Arrays;
public class QuickSort {
public static void quicksort(int[] array, int left, int right) {
if (left >= right) return; // 정렬 하고자 하는 집단의 원소가 1개인 경우
int pi = partition(array, left, right);
quicksort(array, left, pi - 1);
quicksort(array, pi, right);
}
public static int partition(int[] array, int left, int right) {
int pivot = array[(left + right) / 2];
while (left <= right) { // 엇갈릴 때까지 반복
// 오름차순 조건, 내림차순은 반대로 하면됩니다.
while (array[left] < pivot) left++; // 키 값보다 큰 값을 만날 때까지 오른쪽으로 이동
while (array[right] > pivot) right--; // 키 값보다 작은 값을 만날 때까지 왼쪽으로 이동
if(left <= right) { // 현재 엇갈린 상태면 키 값과 교체
swap(array, left, right);
left++;
right--;
}
}
return left;
}
public static void swap(int[] array, int a, int b) {
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
public static void main(String[] args) {
int[] array = { 80, 70, 60, 50, 40, 30, 20 };
quicksort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}
📌병합 정렬
큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 시간복잡도는 O(n log n)
빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.
퀵소트와는 반대로 안정 정렬에 속함
- 다른 정렬 알고리즘과 달리 인접한 값들 간에 상호 자리 교대(swap)이 일어나지 않습니다.
예시를 통해 알아봅시다.
예를 들어, 다음과 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다.
[6, 5, 3, 1, 8, 7, 2, 4]
먼저 하나의 배열을 두 개로 쪼갭니다.
[6, 5, 3, 1] [8, 7, 2, 4]그래고 다시 두 개의 배열을 네 개로 쪼갭니다.
[6, 5] [3, 1] [8, 7] [2, 4]
마지막으로 디시 네 개의 배열을 여덜 개로 쪼갭니다.
[6] [5] [3] [1] [8] [7] [2] [4]이제 더 이상 쪼갤 수가 없으니 두 개씩 합치기를 시작하겠습니다. 합칠 때는 작은 숫자가 앞에 큰 수자를 뒤에 위치시킵니다.
[5, 6] [1, 3] [7, 8] [2, 4]이제 4개의 배열을 2개로 합칩니다. 각 배열 내에서 가장 작은 값 2개를 비교해서 더 작은 값을 먼저 선택하면 자연스럽게 크기 순으로 선택이 됩니다.
[1, 3, 5, 6] [2, 4, 7, 8]최종적으로 2개의 배열도 마찬가지로 크기 순으로 선택하가면서 하나로 합치면 정렬된 배열을 얻을 수 있습니다.
[1, 2, 3, 4, 5, 6, 7, 8]구현
재귀를 이용해서 병합 정렬을 구현할 수 있습니다. 먼저 배열을 더 이상 나눌 수 없을 때 까지 (원소가 하나만 남을 때까지) 최대한 분할 후에, 다시 병합하면서 점점 큰 배열을 만들어 나가면 됩니다. 따라서 이 재귀 알고리즘의 기저 조건은 입력 배열의 크기가 2보다 작을 때이며, 이 조건에 해당할 때는 배열을 그대로 반환하면 됩니다.
import java.util.Arrays;
public class MergeSort {
public static void mergesort(int[] arr, int i, int length) {
sort(arr, 0, arr.length);
}
// mergeSort
private static void sort(int[] arr, int low, int high) {
if(high - low < 2) return;
int mid = (low+high) / 2;
sort(arr, 0, mid);
sort(arr, mid, high);
merge(arr, low, mid, high);
}
// merge
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low];
int t = 0, l = low, h = mid;
while (l < mid && h < high) {
if(arr[l] < arr[h]) {
temp[t++] = arr[l++];
} else {
temp[t++] = arr[h++];
}
}
while (l < mid) {
temp[t++] = arr[l++];
}
while (h < high) {
temp[t++] = arr[h++];
}
for (int i = low; i < high; i++) {
arr[i] = temp[i - low];
}
}
public static void main(String[] args) {
int[] array = { 80, 70, 60, 50, 40, 30, 20 };
mergesort(array, 0, array.length);
System.out.println(Arrays.toString(array));
}
}
차이점
퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)
정리하기
이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.
★★★합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다.★★★
LinkedList를 퀵정렬을 사용해 정렬하면?
성능이 좋지 않음
퀵정렬은, 순차 접근이 아닌 임의 접근이기 때문
LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적임
따라서 임의로 접근하는 퀵소트를 활용하면 오버헤드 발생이 증가하게 됨
배열은 인덱스를 이용해서 접근이 가능하지만, LinkedList는 Head부터 탐색해야 함
배열[O(1)] vs LinkedList[O(n)]
참고사이트 : blog.jupiterflow.com/2020/07/28/algorithm/study/04_quick_sort/
참고사이트 : www.daleseo.com/sort-quick/
참고사이트 : github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/MergeSort.md
'알고리즘 문제 풀이' 카테고리의 다른 글
| [LeetCode] Java 448. Find All Numbers Disappeared in an Array (0) | 2021.05.09 |
|---|---|
| [Algorithm] 힙 정렬 (0) | 2021.04.15 |
| [Algorithm] 선택정렬 / 버블정렬 / 삽입정렬 (1) | 2021.04.15 |
| [Algorithm] 알고리즘 시간복잡도에 대하여 (0) | 2021.04.15 |
