정렬 알고리즘 Sort Algorithm
데이터를 특정한 기준에 따라 순서대로 정렬하는 알고리즘을 의미한다.
특징
- 시간 복잡도
일부 알고리즘은 작은 데이터 집합에 대해 빠르지만, 큰 데이터 집합에서 느릴 수 있다. 시간 복잡도를 고려해 선택해야 한다. - 안정성
안정적인 정렬 알고리즘은 동일한 값의 순서가 바뀌지 않는다. - 추가 메모리 사용
추가적인 메모리를 필요로 하는 경우가 있기 때문에 메모리 효율적인 정렬 알고리즘을 선택할 수 있도록 고려해야한다. - 알고리즘의 복잡성
알고리즘 이해와 구현의 어려움을 의미한다.
종류
- 퀵정렬 (Quick Sort)
분할 정복 방식*을 이용해 배열을 빠르게 정렬하는 알고리즘
대규모 데이터 정렬에 매우 유용. 많은 프로그래밍 언어에서 내장된 정렬 함수에 사용된다.
<< 동작 방식 : 배열에서 하나의 요소(피벗Pivot)를 기준으로 선택. 피벗을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할. 분할된 두 개의 하위 배열에 대해 재귀적으로 위 과정 반복. 더 이상 분할되지 않으면 정렬 완료. >>
평균 시간 복잡도 -> O(nlogn)
최악 시간 복잡도 -> O(n^2)
-> Arrays.sort() : 퀵 정렬을 사용하여 배열을 정렬한다. 기본 타입 배열과 객체 타입 배열 모두에 대해 사용할 수 있다.
-> Collections.sort() : 퀵 정렬을 사용하여 객체를 정렬한다. List, Set, Queue 등의 컬렉션 프레임워크에 대해 사용할 수 있다. - 버블 정렬(Bubble Sort)
인접한 두 원소를 비교하여 큰 값을 오른쪽으로 이동시키는 방식의 정렬 알고리즘
정렬할 원소의 수가 적은 상황이나 많더라도 거의 정렬된 상태일 때 사용. 대부분 다른 정렬 방식보다 느리고 비효율적.
<< 동작 방식 : 배열의 첫 요소부터 인접한 요소와 비교. 인접한 요소의 순서(크기)확인 후 잘못된 상태이면 교환. 배열의 끝까지 이동하며 반복. 한 번의 반복이 끝나면 가장 큰 요소가 배열의 마지막으로 이동. 위의 과정 정렬 완료까지 반복. >>
평균 시간 복잡도 -> O(n^2)
최악 시간 복잡도 -> O(n^2) - 선택 정렬(Selection Sort)
주어진 배열에서 최소값을 찾아 맨 앞 원소와 교환하는 방식의 정렬 알고리즘
원소의 개수가 적거나 이미 거의 정렬된 상태일때 사용. 다른 정렬 방식보다 느리고 비효율적.
<< 동작 방식 : 배열에서 가장 작은 요소 찾기. 가장 작은 요소와 배열의 첫 요소 교환. 두번째로 작은 요소 찾아 두번째 요소와 교환. 배열의 끝까지 해당 과정 반복. >>
평균 시간 복잡도 -> O(n^2)
최악 시간 복잡도 -> O(n^2) - 삽입 정렬(Insertion Sort)
정렬되어 있는 부분집합 내에서 자신이 들어갈 위치를 찾아 삽입하는 방식의 정렬 알고리즘
<< 동작 방식 : 배열의 두번째 요소부터 시작. 현재 위치 요소 기준으로 이전 요소들과 비교. 이전 위치 요소가 현재 위치 요소보다 크면 현재 위치로 이동시킴. 이전 위치 요소가 현재 위치 요소보다 작거나 같으면 정렬 완료로 간주하고 다음 요소로 이동. >>
평균 시간 복잡도 -> O(n^2)
최악 시간 복잡도 -> O(n^2) - 병합 정렬(Merge Sort)
분할 정복 방식을 이용하여 배열을 정렬하는 알고리즘
배열을 반으로 나눠 각각 재귀적으로 정렬. 정렬된 두 배열 병합 단계에서 작은 값 선택해 새로운 배열에 차례로 배치하는 과정 반복.
<< 동작 방식 : 배열 반으로 나눔. 각 반쪽 재귀적 정렬. 정렬된 두 반쪽 병합해 하나의 정렬된 배열로 합침. >>
평균 시간 복잡도 -> O(nlogn)
최악 시간 복잡도 -> O(nlogn) - 힙 정렬(Heap Sort)
힙이라는 자료구조를 이용해 정렬하는 알고리즘.
안정적인 정렬 알고리즘. 평균적으로 다른 정렬 알고리즘에 비해 빠른 실행 시간을 가지지만 추가적인 메모리 공간이 필요하다.
<< 동작 방식 : 주어진 배열을 최대 힙으로 구성. 최대 힙에서 가장 큰 요소(루트)를 가져와 배열의 맨 끝으로 이동. 배열 크기 줄이고 남은 요소 다시 최대 힙 구성. 정렬 완료시까지 해당 과정 반복. >>
평균 시간 복잡도 -> O(nlogn)
최악 시간 복잡도 -> O(nlogn) - 기수 정렬(Radix Sort)
각 자리의 숫자별로 정렬하는 알고리즘
정렬할 숫자를 가장 낮은 자릿수부터 높은 자릿수까지 반복 처리. 숫자를 자릿수별로 그룹으로 나누고 해당 그룹 내에서 정렬 수행. 가장 높은 자릿수까지 반복하여 정렬.
<< 동작 방식 : 정렬 요소들 낮은 -> 높은 자릿수까지 반복 정렬. 각 자릿수 요소들 그룹화. 그룹화된 요소들 순서대로 다시 배열. 정렬 완료시까지 해당 과정 반복. >>
평균 시간 복잡도 -> O(d(n+k))
최악 시간 복잡도 -> O(d(n+k))
정렬 속도
시간 복잡도를 기준으로 아래 순서대로 속도가 빠르다.
퀵 > (Arrays.sort() > Collections.sort()) > 버블 > 선택 > 삽입 > 병합 > 힙 > 기수 정렬
구현
정렬의 특성상 아래 함수를 알아두면 편리하다. 앞으로 나올 정렬의 구현에서도 이용된다.
public static void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
- 퀵 정렬
public static void sortByQuickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int left, int right) {
int part = partition(arr, left, right);
if (left < part - 1) {
quickSort(arr, left, part - 1);
}
if (part < right) {
quickSort(arr, part, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[(left + right) / 2];
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
return left;
}
- 버블 정렬
public static void sortByBubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
- 선택 정렬
public static void sortBySelectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr, i, minIdx);
}
}
- 삽입 정렬
public static void sortByInsertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && tmp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
- 셀 정렬
public static void sortByShellSort(int[] arr) {
for (int h = arr.length / 2; h > 0; h /= 2) {
for (int i = h; i < arr.length; i++) {
int tmp = arr[i];
int j = i - h;
while (j >= 0 && arr[j] > tmp) {
arr[j + h] = arr[j];
j -= h;
}
arr[j + h] = tmp;
}
}
}
- 합병 정렬
public static void sortByMergeSort(int[] arr) {
int[] tmpArr = new int[arr.length];
mergeSort(arr, tmpArr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int[] tmpArr, int left, int right) {
if (left < right) {
int m = left + (right - left) / 2;
mergeSort(arr, tmpArr, left, m);
mergeSort(arr, tmpArr, m + 1, right);
merge(arr, tmpArr, left, m, right);
}
}
public static void merge(int[] arr, int[] tmpArr, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
tmpArr[i] = arr[i];
}
int part1 = left;
int part2 = mid + 1;
int index = left;
while (part1 <= mid && part2 <= right) {
if (tmpArr[part1] <= tmpArr[part2]) {
arr[index] = tmpArr[part1];
part1++;
} else {
arr[index] = tmpArr[part2];
part2++;
}
index++;
}
for (int i = 0; i <= mid - part1; i++) {
arr[index + i] = tmpArr[part1 + i];
}
}
- 힙 정렬
public static void sortByHeapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i < arr.length; i++) {
heapify(arr, i, arr.length - 1);
}
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i - 1);
}
}
public static void heapify(int[] arr, int parentIdx, int lastIdx) {
int leftChildIdx;
int rightChildIdx;
int largestIdx;
while (parentIdx * 2 + 1 <= lastIdx) {
leftChildIdx = (parentIdx * 2) + 1;
rightChildIdx = (parentIdx * 2) + 2;
largestIdx = parentIdx;
if (arr[leftChildIdx] > arr[largestIdx]) {
largestIdx = leftChildIdx;
}
if (rightChildIdx <= lastIdx && arr[rightChildIdx] > arr[largestIdx]) {
largestIdx = rightChildIdx;
}
if (largestIdx != parentIdx) {
swap(arr, parentIdx, largestIdx);
parentIdx = largestIdx;
} else {
break;
}
}
}
* 분할 정복
큰 문제를 작은 문제로 나누어서 해결하는 알고리즘. 분할 -> 정복 -> 결합 단계로 처리
'Algorithm' 카테고리의 다른 글
| [Algorithm] 프로그래머스 - 이중우선순위큐 (0) | 2024.04.23 |
|---|---|
| [Algorithm] 프로그래머스 고득점 kit - 전화번호 목록 (0) | 2024.03.17 |
| [Algorithm] 프로그래머스 정렬 - 가장 큰 수 (0) | 2024.03.10 |
| [Algorithm] 프로그래머스 정렬 - HIndex (0) | 2024.03.10 |
| [Algorithm] 바킹독 0x04 - 연결리스트 (0) | 2024.02.06 |
