정렬의 개념
📌버블 정렬(Bubble Sort)
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
인접한 2개의 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 유사하다.로직
1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 마지막 - 1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
private static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 1
for (int j = 0; j < arr.length - i - 1; j++) { // 2
if (arr[j] > arr[j + 1]) { // 3
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.print((i + 1) + "단계 : ");
print(arr);
}
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 6 2 4 3 7 1 9
2단계 : 2 4 3 6 1 7 9
3단계 : 2 3 4 1 6 7 9
4단계 : 2 3 1 4 6 7 9
5단계 : 2 1 3 4 6 7 9
6단계 : 1 2 3 4 6 7 9
7단계 : 1 2 3 4 6 7 9 장점
구현이 간단하고 소스코드가 직관적이다.
이미 정렬된 데이터를 정렬할 때, 가장 빠르다.
정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
안정 정렬이다.
단점
시간 복잡도가 최악, 최선, 평균 모두 O(N^2)이므로 비효율적이다.
다른 정렬에 비해 정렬 속도가 느리다.
교환 횟수가 많다.
역순배열을 정렬할 때, 가장 느리다.
📌병합 정렬(Merge Sort)
빠른 정렬로 분류되며, Quick Sort와 함께 많이 언급되는 정렬 방식이다.
Quick Sort와는 반대로 안정 정렬에 속한다.로직
1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 마지막 - 1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
private static void mergeSort(int[] a, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(a, left, mid); // 왼쪽 부분 배열을 나눈다.
mergeSort(a, mid + 1, right); // 오른쪽 부분 배열을 나눈다.
merge(a, left, mid, right);
// 나눈 부분 배열을 합친다.
// 핵심 로직이다.
}
}
/*
* i : 왼쪽 부분 배열을 관리하는 인덱스
* j : 오른쪽 부분 배열을 관리하는 인덱스
* */
private static void merge(int[] a, int left, int mid, int right) {
int i, j, k, l;
i = left;
j = (mid + 1);
k = left;
// 왼쪽 부분 배열과 오른쪽 부분 배열을 비교하면서
// 각각의 원소 중에서 작은 원소가 sorted 배열에 들어간다.
// 왼쪽 혹은 오른쪽의 부분 배열 중 하나의 배열이라도 모든 원소가 sorted 배열에 들어간다면
// 아래의 반복문은 조건을 만족하지 하지 않기 때문에 빠져 나온다.
// sorted 배열에 들어가지 못한 부분 배열은 아래 쪽에서 채워진다.
while (i <= mid && j <= right) {
if (a[i] < a[j]) sorted[k++] = a[i++];
else sorted[k++] = a[j++];
}
// mid < i 인 순간, i는 왼쪽 부분 배열의 인덱스를 관리하므로
// 즉, 왼쪽 부분 배열이 sorted 에 모두 채워졌음을 의미한다.
// 따라서 남아 있는 오른쪽 부분 배열의 값을 일괄 복사한다.
if (mid < i) {
for (l = j; l <= right; l++) sorted[k++] = a[l];
} else {
// mid > i 인 것은 오른쪽 부분 배열이 sorted 배열에 정렬된 상태로 모두 채워졌음을 의미한다.
// 따라서, 왼쪽 부분 배열은 아직 남아 있는 상태이다.
// 즉, 남아 있는 왼쪽 부분 배열의 값을 일괄 복사한다.
for (l = i; l <= mid; l++) sorted[k++] = a[l];
}
// sorted 배열에 들어간 부분 배열을 합하여 정렬한 배열은
// 원본 배열인 a 배열로 다시 복사한다.
for (l = left; l <= right; l++) a[l] = sorted[l];
}장점
데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. -> O(N logN)
크기가 큰 레코드를 정렬한 경우, LinkedList를 사용한다면 병합 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.
안정 정렬에 속한다.
단점
레코드를 배열로 구성한다면, 임시 배열이 필요하다.
메모리 낭비를 초래한다.
제자리 정렬이 아니다.
레코드의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
📌삽입 정렬(Intersection Sort)
손 안의 카드를 정렬하는 방법과 유사하다.
새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.
2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
최선의 경우, O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.로직
정렬은 2번째 위치(index)의 값을 standard에 저장한다
standard와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.
1번으로 돌아가서 다음 위치(index)의 값을 standard에 저장하고 이 과정을 반복한다.
private static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) { // 1
int standard = arr[i];
int index = i - 1;
while ((0 <= index) && standard < arr[index]) {//2
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = standard; // 3
print(arr, i);
}
}
private static void print(int[] arr, int step) {
System.out.print(step + "단계 : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 6 7 2 4 3 9 1
2단계 : 2 6 7 4 3 9 1
3단계 : 2 4 6 7 3 9 1
4단계 : 2 3 4 6 7 9 1
5단계 : 2 3 4 6 7 9 1
6단계 : 1 2 3 4 6 7 9장점
알고리즘이 단순하다.
대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
선택 정렬이나 버블 정렬에 비하여 상대적으로 빠르다.
단점
비교적 많은 수들의 이동을 포함한다.
비교할 수가 많고 크기가 클 경우에 적합하지 않다.(배열의 길이가 길어질수록 비효율적)
평균과 최악의 시간 복잡도가 O(N^2)이므로 비효율적이다.
📌선택 정렬(Selection Sort)
해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순 정렬)과 최대 선택 정렬(내림차순 정렬)로 나뉜다.로직
주어진 배열에서 첫번째 인덱스를 기준으로 잡는다. 기준은 처음부터 시작한다.
주어진 배열에서 기준 이후의 값 중 최소값을 찾는다.
최소값과 그 기준의 값을 교체한다.
기준 이후의 나머지 배열을 같은 방법으로 교체한다.
int[] arr = {7, 6, 2, 4, 3, 9, 1};
private static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 1
int standard = i;
for (int j = i + 1; j < arr.length; j++) { // 2
if (arr[j] < arr[standard]) standard = j; // 3
}
// 4
int temp = arr[standard];
arr[standard] = arr[i];
arr[i] = temp;
print(arr);
}
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 1 6 2 4 3 9 7
2단계 : 1 2 6 4 3 9 7
3단계 : 1 2 3 4 6 9 7
4단계 : 1 2 3 4 6 9 7
5단계 : 1 2 3 4 6 9 7
6단계 : 1 2 3 4 6 7 9
7단계 : 1 2 3 4 6 7 9 장점
알고리즘이 단순하다.
정렬을 위한 비교는 여러번 수행되지만, 실제로 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적인 면이 있다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
단점
시간 복잡도가 O(N^2)이므로 비효율적이다.
불안정 정렬(Unstable Sort)이다.
