1. 정렬 알고리즘
컴퓨터 과학에서 가장 많이 사용되는 연산 중 하나일 만큼 데이터를 활용함에 있어 정렬은 매우 중요하다.
예를 들자면, 당장 이 글을 쓰고 있는 티스토리에서도 글이 수백 개가 넘어간다면 카테고리별 혹은 날짜별 같은 특정한 정렬 기준에 따라 나열되어 있지 않다면 사람이 찾을 때도, 컴퓨터가 찾을 때도 많은 시간을 요구한다.
정렬 방법은 정렬이 수행될 때 데이터가 저장되어 있는 위치에 따라 내부 정렬, 외부 정렬로 구분한다.
내부 정렬은 데이터의 용량이 주기억장치(RAM) 저장 공간보다 작을 때 수행하는 정렬 방법이며 다양한 알고리즘에서 흔하게 사용되고 있는 정렬 방법이다.
외부 정렬은 내부 정렬의 반대의 케이스로 데이터를 보조 기억장치(HDD, SSD)에 저장하고 일부 데이터만 주기억장치에 넣어가며 정렬하는 방식으로 대치 선택, 다단계 합병 정렬 등이 있으나 여기서는 내부 정렬만 다룬다. (솔직히 아직 자신이 없다 ....)
1-1 선택 정렬
선택 정렬은 주어진 데이터에서 가장 작은 값을 선택해 앞쪽부터 채워 나가는 정렬 방법이다.
데이터를 모두 확인하기 때문에 항상 일정한 수행 시간을 갖고 있으며 구현 방식이 쉬워 적은 양의 데이터에서 사용하기 효율적인 정렬 방식이다.
Java 예제
static void selectionSort(int[] A) {
for (int i = 0; i < A.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < A.length; j++) {
if (A[minIdx] > A[j]) minIdx = j; // 가장 작은값의 인덱스를 찾는다.
}
// 가장 작은값의 인덱스를 i번째 인덱스와 교체한다.
int tmp = A[minIdx];
A[minIdx] = A[i];
A[i] = tmp;
}
System.out.println(Arrays.toString(A));
}
매번 전체 배열 중 최솟값을 찾아 앞에서부터 찾아나가기 때문에 시간 복잡도는 O(n²)으로 효율성이 좋다고 볼 수 없다.
1-2 버블 정렬
삽입 정렬이 작은 값부터 정렬을 했다면 버블 정렬은 데이터의 시작점부터 끝점까지 이동하며 인접한 인덱스를 비교해 나가며 큰 값부터 채워나가는 정렬 방식이다.
Java 예제
static void bubbleSort(int[] A) {
boolean chk = false; // 위치 변경여부 확인 boolean
for (int i = 0; i < A.length - 1; i++) {
for (int j = 1; j < A.length - i; j++) {
if (A[j] < A[j - 1]) {
chk = true;
int tmp = A[j - 1];
A[j - 1] = A[j];
A[j] = tmp;
}
}
if (!chk) break; // 정렬이 일어나지 않았으니 완료되었다고 볼 수 있음.
}
System.out.println(Arrays.toString(A));
}삽입 정렬과 마찬가지로 매번 n - 1, n - 2... 만큼 연산이 필요하여 O(n²)으로 효율성이 좋지는 않다.
1-3 삽입 정렬
삽입 정렬은 하나의 데이터를 정렬된 구간과 비 정렬된 구간으로 나누어 비 정렬된 구간의 데이터를 하나 뽑아 정렬 구간의 데이터와 비교해나가며 본인의 자리를 찾아 삽입하는 정렬 방식이다.
Java 예제
static void insertionSort(int[] A) {
System.out.println(Arrays.toString(A));
for (int i = 1; i < A.length; i++) {
int tmp = A[i]; // 비정렬구간 선택 데이터
int j = i - 1; // 선택 데이터 바로 좌측부터 왼쪽으로 비교를 시작한다.
while(j >= 0 && A[j] > tmp) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = tmp;
}
System.out.println(Arrays.toString(A));
}앞선 두 개의 정렬 방식과 마찬가지로 시간 복잡도는 O(n²)으로 동일하지만 입력 데이터가 거의 원하는 대로 이미 정렬된 채로 주어지면 O(n)으로 그 어떤 정렬 알고리즘보다 빠르게 동작한다.
1-4 퀵 정렬
퀵 정렬은 피벗이라는 특정 데이터를 선택하여 분할하는 과정을 반복해나가며 입력 데이터를 정렬한다.
Java 예제
static void quickSort(int[] A, int L, int R) {
if (L >= R) return;
int pivot = quickSortPartition(A, L, R);
quickSort(A, L, pivot - 1); // pivot 기준 왼쪽 배열 정렬
quickSort(A, pivot + 1, R); // pivot 기준 오른쪽 배열 정렬
}
// 수행마다 피봇을 기준으로 쪼개진 배열을 정렬한다!
static int quickSortPartition(int[] A, int L, int R) {
int pivot = A[L]; // 제일 좌측값을 피봇으로 한다.
int i = L, j = R;
while (i < j) {
while (pivot < A[j]) j--; // 피봇보다 작은 값을 찾을때까지 R을 이동한다.
while (i < j && pivot >= A[i]) i++; // 피봇보다 큰 값을 찾을 때까지 L을 이동한다.
if (i < j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
// 피봇을 기준으로 또 쪼개기 위해 피봇의 위치를 바꿔준다!
A[L] = A[i];
A[i] = pivot;
return i;
}앞선 세 가지의 정렬 방법은 모두 O(n²)의 시간 복잡도를 갖고 있으며 매우 간단한 알고리즘이었다.
하지만 퀵 정렬은 피벗의 임의성만 보장된다면 평균적으로 O(nlogn)의 시간 복잡도 보일 가능성이 높은 비교 기반 알고리즘이다.
1-5 합병 정렬
앞서 설명한 퀵 정렬은 특정 데이터를 피벗으로 선정하는 기준에서 부분 배열로 나눌 때 불균형하게 나뉘어 최악의 경우 O(n²)의 시간 복잡도가 나타나지만 합병 정렬은 항상 균일하게 나누기 때문에 O(nlogn)의 시간 복잡도를 보이는 정렬 방법이다.
