오늘은 정렬 알고리즘 중에 단순 선택 정렬, 단순 삽입 정렬에 대해 알아보자.
📘 단순 선택 정렬
단순 선택 정렬(straight selection sort) 알고리즘은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.
✏ 단순 선택 정렬 원리
그림을 통해 알아보자.
단순 선택 정렬은 가장 작은 요소부터 정렬하기 때문에 가장 작은 1을 선택해 정렬을 시작한다.
그럼 1과 5의 위치가 바뀌게 된다.
그 다음으로 작은 요소인 2를 선택하여 3과 위치를 바꾼다.
그러면 2와 3의 위치가 바뀌게 된다.
이런식으로 순차적으로 다 정렬이 될때까지 작은 요소 순으로 선택하여 정렬하는 방식이 되는 것이다.
✏ 단순 선택 정렬 코드
단순 선택 정렬 알고리즘을 코드로 한번 짜보자.
일단 단순 선택 정렬의 교환 과정은 이렇다
1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값 a[min]을 선택한다.
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.위와 같은 과정을 n - 1회 반복을 하면 정렬이 완성된다.
알고리즘을 구성해보면
for (int i = 0; i < n - 1; i++) {
// min = a[i], ... , a[n - 1]에서 가장 작은 값을 가지는 요소의 인덱스
// a[i]와 a[min]의 값을 교환
}위처럼 구성하면 될것이다.
전체 사용되는 메서드로는 이렇게 두가지가 있을 것이다.
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void selectSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
swap(a, i, min);
}
}단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n^2 - n) / 2회이다.
그런데 이는 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.
단순 삽입 정렬의 시간복잡도는 O(n^2)이다.
📘 단순 삽입 정렬
단순 삽입 정렬(straight insertion sort)은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷해보이지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다르다.
✏ 단순 삽입 정렬 원리
그림으로 알아보자.
단순 삽입 정렬은 2번째 요소부터 선택하여 진행한다.
이때 3은 5보다 앞쪽에 위치해야 하므로 앞쪽에 삽입한다. 이 상태에서 5를 오른쪽으로 밀면 아래와 같이 된다.
다음엔 3번째 요소인 2를 선택해 앞쪽에 삽입한다. 그 이후에도 반복하여 같은 작업을 수행하면 된다.
✏ 단순 삽입 정렬 코드
코드를 통해 알아보자.
알고리즘을 살펴보면 i를 1, 2, ..., n - 1로 1씩 증가하면서 인덱스가 i인 요소를 꺼내 알맞은 곳에 삽입한다.
코드로 나타내면 아래와 같다.
for (int i = 1; i < n; i++) {
// tmp <- a[i]
// a[0], ..., a[i - 1]의 알맞은 곳에 tmp를 삽입한다.
}tmp에 a[i]를 대입하고 반복 제어용 변수 j에 i - 1을 대입한 다음 아래의 두 조건 중 하나를 만족할 때까지 j를 1씩 감소하면서 대입을 반복해서 한다.
1. 정렬된 열의 왼쪽 끝에 도달
2. tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견이때 드모르간 법칙을 적용하면 아래의 두 조건이 모두 성립할 때까지 반복한다고 할 수 있다.
1. j가 0보다 크다.
2. a[j - 1] 값이 tmp보다 크다.이 모든 과정을 마치고 난 다음 요소 a[j]에 tmp를 대입하면 한 요소에 대한 단순 삽입 정렬을 마치게 된다.
주요 메서드는 다음과 같다.
static void insertSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
int j;
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}단순 삽입 정렬 알고리즘은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적인 알고리즘이라 할 수 있다. 요소의 비교 횟수와 교환 횟수는 n^2 / 2회이다.
단순 삽입 정렬의 시간 복잡도는 O(n^2)이다.
