한국방송통신대 알고리즘 강의 3강 정리노트입니다.
정렬이란?
주어진 데이터를 값의 크기 순서에 따라 오름차순 혹은 내림차순으로 재배치하는 것이다.
정렬 수행 시점에 데이터가 어디에 저장되어 있으냐에 따라 내부 정렬, 외부 정렬로 구분한다.
- 내부 정렬: 전체 데이터를 주기억장치에 저장한 후, 정렬을 수행
- 외부 정렬: 모든 데이터를 주기억장치에 저장할 수 없을 때, 모든 데이터를 보조기억장치에 저장해 두고, 일부 데이터만을 반복적으로 주기억장치로 옮겨와 정렬을 수행하는 방식
내부 정렬 알고리즘
비교 기반 알고리즘
값을 비교하여 정렬을 수행한다. 일반적으로 수행하는 정렬 알고리즘이다.
- 선택, 버블, 삽입, 셸 - O(n²)
- 퀵, 합병, 힙 - O(n log n)
- 알고리즘의 성능: 키 값의 비교 횟수
데이터 분포 기반 알고리즘
- 계수, 기수, 버킷 - O(n)
- 알고리즘의 성능: 데이터의 이동 횟수
안정적 정렬 stable sorting
안정적인 정렬은 두 개의 동일한 값이 있을 때, 정렬 후에도 상대적인 위치가 정렬 후에도 바뀌지 않고 유지되는 정렬이다.
- 버블, 삽입, 병합
제자리 정렬 in-place sorting
입력 배열 외에 별도로 필요한 저장 공간이 상수를 넘지 않는다. 데이터를 정렬하는 과정에서 원본 배열을 변경하여 추가적인 메모리 공간을 거의 사용하지 않는다.
선택 정렬 Selection Sort
입력 배열에서 가장 작은 값부터 순서대로 선택하여 나열하는 방식이다.
- 데이터의 개수만큼 반복한다.
- 미정렬 부분에서 최솟값을 찾는다
- 최솟값과 미정렬 맨 앞의 위치를 교환한다.
public static void selectionSort(int[] arr) {
int n = arr.length;
// 배열의 맨 앞부터 정렬해나감
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 현재 위치를 최소값 위치로 설정
// 현재 위치 이후의 값들과 비교해 가장 작은 값 찾기
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 가장 작은 값과 현재 위치 값 교환
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}특징
- 반복이 중첩되어 O(n²)의 시간 복잡도를 가진다.
- 입력 데이터의 순서에 민감하지 않다. 항상 동일한 성능을 가진다.
- 제자리 정렬 알고리즘이므로 저장 공간은 상수를 넘지 않는다.
- 안정적이지 않은 정렬 알고리즘이다.
버블 정렬 Bubble Sort
모든 인접한 두 데이터를 차례대로 비교하여 왼쪽 데이터가 더 큰 경우에 오른쪽 데이터와 자리를 바꾸는 과정(swap)을 매 단계 반복하여 정렬을 수행한다.
- 왼쪽에서 오른쪽으로 진행 시, 가장 큰 값부터 오른쪽 끝에 위치 시킨다.
- 오른쪽에서 왼쪽으로 진행 시, 가장 작은 값부터 왼쪽 끝에 위치 시킨다.
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 총 n-1번 반복
for (int i = 0; i < n - 1; i++) {
// 각 회전마다 인접한 두 수를 비교하고 필요 시 교환
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// arr[j]와 arr[j+1]를 swap한다
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}특징
- 반복이 중첩되어 O(n²)의 시간 복잡도를 가진다.
- 안정적인 정렬 알고리즘이다.
- 제자리 정렬 알고리즘이므로 저장 공간은 상수를 넘지 않는다.
- 선택 정렬에 비해 데이터 교환이 많이 발생하여 비효율적이다. 최적화를 진행할 수 있다.
버블 정렬 최적화
- 자리 바꿈이 발생하지 않으면 이미 정렬된 상태이므로 이후 처리 단계를 수행하지 않는다.
- 이미 제자리에 있는 데이터에 대해서는 비교를 수행하지 않는다.
- 입력 데이터의 상태에 따라 성능이 달라진다.
- 최악의 경우: 원하는 순서의 역순으로 주어진 경우 -> O(n²)
- 최선의 경우: 원하는 순서의 정렬된 상태로 주어진 경우 -> O(n)
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean isSorted = true; // 정렬된 상태로 가정
for (int j = 0; j < n - 1 - i; j++) { // 왼쪽 -> 오른쪽
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 자리바꿈 -> 미정렬
isSorted = false;
}
}
// 이미 정렬된 상태이므로 종료
if (isSorted) {
break;
}
}
}삽입 정렬 Insertion Sort
주어진 데이터를 하나씩 뽑은 후, 이미 나열된 데이터가 항상 정렬된 상태를 유지하도록 바른 위치에 삽입하여 나열하는 방식이다.
입력 배열을 정렬 부분과, 미정렬 부분으로 구분하여 처리한다.
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 현재 삽입할 값
int j = i - 1;
// 정렬된 부분에서 적절한 위치 찾기
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 오른쪽으로 한 칸씩 밀기
j--;
}
arr[j + 1] = key; // 올바른 위치에 삽입
}
}특징
- 반복이 중첩되어 O(n²)의 시간 복잡도를 가진다.
- 안정적인 정렬 알고리즘이다.
- 제자리 정렬 알고리즘이므로 저장 공간은 상수를 넘지 않는다.
- 입력 데이터의 상태에 따라 성능이 달라진다.
- 최악의 경우: 원하는 순서의 역순으로 주어진 경우 -> O(n²)
- 최선의 경우: 원하는 순서의 정렬된 상태로 주어진 경우 -> O(n)
셸 정렬
삽입 정렬의 단점을 보완했다 (현재 삽입하고자 하는 데이터가 삽입될 위치에서 많이 벗어나 있어도 한 번에 한 자리씩 이동하여 자리를 찾는 단점)
- 멀리 떨어진 데이터와의 비교/교환으로 한 번에 이동할 수 있는 거리를 늘려서 처리 속도 향상
- 처음에 멀리 떨어진 두 데이터를 비교/교환하고, 점차 가까운 위치의 데이터를 비교/교환, 마지막에는 인접한 데이터를 비교/교환한다.
- 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜가며 반복한다.
부분배열의 개수
- 임의의 순열을 사용하여 (h_k)부터 (h_1)까지의 양수 순열을 적용한다.
- k는 배열 요소 개수, 각 부분 배열 내에서 이웃한 데이터간의 거리 (Distance, gap)
public static void shellSort(int[] arr) {
int n = arr.length;
// gap 설정 (일반적으로 n/2)
for (int gap = n / 2; gap > 0; gap /= 2) {
// gap만큼 떨어진 요소들끼리 삽입 정렬 수행
for (int i = gap; i < n; i++) {
int temp = arr[i]; // 현재 위치 값 보관
int j = i;
// 앞쪽 요소들과 비교하며 정렬 위치 찾기
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]; // 앞쪽 요소를 뒤로 이동
j -= gap;
}
arr[j] = temp; // 올바른 위치에 삽입
}
}
}- 하나의 입력 배열을 물리적으로 부분배열로 분할한 것은 아님
- 각 부분배열을 번갈아가며 미정렬 부분의 첫 번째 데이터를 뽑은 후, gap만큼 떨어진 정렬 부분에서 제자리를 찾아 삽입한다.
특징
- 사용하는 순열에 따라 성능이 달라진다. 가장 좋은 간격은 미지수.
- 최선: O(n log n), 최악: O(n²)
- 안정적이지 않은 정렬 알고리즘이다.
- 제자리 정렬 알고리즘이므로 저장 공간은 상수를 넘지 않는다.
안녕하세요.