삽입 정렬(Insertion Sort)
삽입 정렬은 선택 정렬(Seletct Sort)과 함께 가장 많이 사용되는 정렬 방법이자 아주 간단한 정렬 방법이다.
선택 정렬이 많은 비교와 적은 교환으로 특정지워 진다면(이 값이 가장 작은 값인지 계속 확인하니까) 삽입 정렬은 반대로 적은 비교와 많은 교환으로 직정지워진다.
삽입 정렬의 전략
삽입 정렬은 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 종작을 반복적으로 하는 정렬 방법이다.
즉 이미 정렬이 끝낸 앞부분에다가, 정렬해야할 값이 어디에 들어가면 좋을지 찾고 삽입하는 정렬이다.
삽입 정렬의 알고리즘을 정의해보면 아래와 같은 순서로 나타낼 수 있다.
- i = 1;
- j = i;
- a[j-1] > a[j] && j > 0인 동안
3-1. a[j] = a[j-1] // 큰값을 뒤로 한칸 이동
3-2. j를 1 감소 - a[j] = a[i] //적절한 공간에 a[i]를 삽입
- i를 1증가하고 2번으로 돌아간다
위 알고리즘에 의하면 배열에서 i항 이하는 이미 정렬이 완료된 상태가 되고, i항을 적절한 위치에 삽입하는 동작은 j변수를 통해서 구현한다.
삽입 정렬의 실제
잘 이해가 안되면 "TOLEARNSORTALGORITHM" 문자열을 삽입 정렬하는 과정을 따라가보자!
처음 i가 1일때는 a[i]는 O가 되며, 이 O는 T앞에 삽입되고, 이제 a[0] ~ a[1]까지는 이미 정렬이 완료가 된 상태가 된다!
이제 i가 2가 되어서 a[i]는 L이 되는데 이는 O앞에 삽입된다. 이제 a[0] ~ a[2]까지 정렬이 완료가 된 상태가 된다!
다시 i는 3이 되고 a[3]은 E가되고, 이는 L앞에 삽입된다. 이제 a[0] ~ a[3]까지는 정렬이 완료가 된다.
위 과정을 반복하면 결과적으로 정렬이 완료되게 된다.
삽입정렬은 이러한 알고리즘이기 때문에 안정성이 있다.
위 영상을 마지막까지 다 보면 확인이 가능하겠지만, T값에 대해서 1,2,3 순서대로 숫자를 붙여두었는데 이 숫자가 유지되는걸 볼 수 있다.
C로 구현한 삽입 정렬
void insert_sort(int a[], int n) {
int j;
int temp;
for(int i = 1; i < n; i++) {
j = i;
temp = a[i];
while(j > 0 && a[j-1] > temp) {
// 배열의 모습이 [3, 2] 이라고 할때
// 3을 한칸 뒤로 밀어서 2가 있는 자리로 위치 시킴
a[j] = a[j-1];
j--;
}
// 결과적으로 j는 0부터 i까지 중에서 가장 작은 값이 있는 위치가 됨
a[j] = temp;
}
}위 코드를 보면 temp라는 변수가 불필요한거라는걸 알 수 있다.
실제로 temp대신 a[i]로 대체하고 없애도 된다.
하지면 굳이 temp를 쓰는 이유는 속도를 향상시키기 위해서이다.
while 루프 내부는 insert_sort 함수에서 가장 많이 수행되는 부분인데, 이 부분에서 a[i]를 쓰는것과 단순히 temp를 쓰는거는 많은 차이가 있다.
a[i]를 쓸 경우 컴파일러에는 a의 주소값을 읽어서 i를 더하는 식의 복잡한 처리를 하지만, 단순히 temp를 사용할때는 temp의 값을 읽어오는 것으로 끝난다.
추가적으로 삽입 정렬은 안정성이 있다고 이야기했는데 그것도 항상 그런것은 아니기 때문에 주의해야 한다.
while의 조건중에서 a[j-1] > temp 라는 부분이 안정성을 결정하는 핵심적인 부분이다.
사실 정렬을 하기위해서는 a[j-1] >= temp 라고 써도 지장은 없다, 다만 >= 를 사용하면 안정성이 깨진다.
즉 상대적으로 가장 뒤에 있는 키가 정렬 후에는 가장 앞으로 가게 되는데, 이렇게 비교하는 조건에 =의 유무에 따라서 안정성을 결정하는 수가 많기에 신경써야 한다.
삽입 정렬의 분석
삽입정렬은 입력 자료에 굉장히 민감하다.
입력 자료의 정렬된 정도에 따라 효율이 좋을수도 있고 안좋을 수도 있다.
삽입 정렬은 교환 횟수가 적고 비교 횟수가 많은 선택 정렬과는 반대로, 비교 횟수는 적고 교환 횟수는 많다.
따라서 큰 레코드(덩어리가 큰 구조물, 파일)를 정렬할 때에는 삽입 정렬은 부적절 하다.
삽입 정렬은 작은 레코드의 배열에 사용하면 뛰어난 성능을 발휘하지만, 큰 레코드에 대해 삽입 정렬을 사용하려면 간접 정렬 방법을 이용하는 방법이 있다.
삽입 정렬은 값을 교환하는 횟수가 많다.
따라서 교환해야하는 값이 단순한 숫자가 아니라 덩치가 큰 구조체, 클레스, 파일 등등 이라면 삽입 정렬은 부적절할 수 있다!
따라서 이럴때는 실제 값을 교환하는게 아닌, 값의 상대적인 위치인 index를 정렬하는 간접 정렬 방법을 사용해도 좋다는 이야기다.
마지막으로 삽입 정렬은 O(N^2)의 성능을 나타내는데, 위 코드를 통해서도 알겠지만 이중 루프가 사용되기 때문이다.
삽입 정렬 최적화
삽입 정렬을 최적화 하기 위해서 보초(sentinel)를 사용해 내부 루프를 간단하게 만들수 있다!
만약 정렬해야할 값들이 일정한 범위 내에 있다면 이 보초(sentinel) 기법을 고려해봄직 하다.
예를 들어서 정렬해야할 값들이 양의 정수(unsigned int)만 다룬다면, 이 배열의 첫번째 요소 a[0]을 -1과 같은 값을 집어넣고, 실제 데이터들은 a[1] 이후에 저장하도록 한다.
그렇다면 insert_sort 함수의 while루프 조건문에 j > 0과 같은 비교문 하나를 삭제할 수 있다.
void sentinel_insert_sort(int a[], int n) {
int j;
int temp;
for(int i = 2; i < n; i++) {
j = i;
temp = a[i];
while(a[j-1] > temp) {
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}j > 0이 없어진것과 i의 변동 범위가 달라진것 외에는 insert_srot 함수와 다른것이 없다.
만약 j > 0이 없다면 배열의 키값중 가장 작은 값이 삽입될때 이값이 배열의 경계를 넘어서 엉뚱한 곳에 삽입되지 않을까!? 하는 우려가 있을수 있다.
하지만 a[0]은 이 경계를 벗어남을 방지하는 보초(sentinel)다.
a[0]에는 -1이 들어있고 배열에는 양의 정수만 들어있으므로, 예를 들어 가장 작은수 1이 삽입될 곳을 찾기위해 j가 계속 줄어든다고 할지라도, a[0]에 저장된 -1 보다는 1이 더 크므로 -1뒤에 1이 삽입이 된다.
따라서 이렇게 a[0]은 경계를 벗어남을 막아주면서 동시에 j > 0과 같은 비교문을 하나 없앨 수 있게된다.
하지만 항상 이런 보초(sentinel)를 사용할수 있는건 아닌데, 많은 경우에 정렬을 해야할 데이터들의 최소값이 정해져있지 않기 때문이다.
또 추가적으로, 삽입 정렬의 경우 현재 삽입하려는 키(i)의 앞부분은 이미 정렬이 완료된 상태다.
따라서 이부분을 linear search가 아닌 binary search를 통해서 더 빠르게 삽입되어야할 위치를 찾는 방법또한 있다.
나중에 binary search또한 공부해서 포스팅해보자.
간접 정렬(Indirect Sort)
삽입 정렬에서 간접 정렬(Indirect Sort)를 고려하는 이유는 삽입 정렬이 비교 횟수는 적지만 교환 횟수가 많기 때문이다.
간접 정렬을 레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스(index) 배열을 조작하는 방법이다.
void indirect_insert_sort(int a[], int index[], int n) {
int j;
int temp;
for(int i = 0 ; i < n; i++) {
index[i] = i;
}
for(int i = 1; i < n; i++) {
j = i;
temp = index[i];
while(a[index[j-1]] > a[temp] && j > 0) {
index[j] = index[j-1];
j--;
}
index[j] = temp;
}
}
void re_arrange(int a[], int index[], int n) {
int *p;
p = (int *)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++) {
p[i] = a[index[i]];
}
for(int i = 0; i < n; i++) {
a[i] = p[i];
}
}따라서 a배열을 직접적으로 조작하지 않고, a배열값의 index만 조정하는 방법이다.
그러면 큰 단위의 실제 값을 변경하지 않고, 단순히 index만 조정하기 때문에 더 부담없이 정렬을 할 수 있게 된다.
즉 결과적으로 a배열은 정렬되지 않고, index배열만 "해당 위치에 와야할 값의 위치를 나타내는 인덱스"가 정렬되게 된다.
이후에 실질적으로 a배열을 정렬하고 싶다면 re_arrange 함수를 이용하면 되는데, index의 순서대로 다시 값을 채워넣기만 하면 된다.
전체 코드
//
// main.c
// Insertion Sort
//
// Created by 박재현 on 2024/05/31.
// A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void print_array(int a[], int n, char option) {
printf("\n");
for(int i = 0; i < n; i++) {
if(option == 'c') {
printf("%c ", a[i]);
} else if(option == 'd') {
printf("%d ", a[i]);
} else if(option == 'b') {
printf("%c(%d) ", a[i], a[i]);
} else if(option == 'i') {
printf("%c(%d) ", a[i], i);
}
}
printf("\n\n");
}
void insert_sort(int a[], int n) {
int j;
int temp;
for(int i = 1; i < n; i++) {
j = i;
temp = a[i];
while(j > 0 && a[j-1] > temp) {
// 배열의 모습이 [3, 2] 이라고 할때
// 3을 한칸 뒤로 밀어서 2가 있는 자리로 위치 시킴
a[j] = a[j-1];
j--;
}
// 결과적으로 j는 0부터 i까지 중에서 가장 작은 값이 있는 위치가 됨
a[j] = temp;
}
}
void sentinel_insert_sort(int a[], int n) {
int j;
int temp;
for(int i = 2; i < n; i++) {
j = i;
temp = a[i];
while(a[j-1] > temp) {
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
void indirect_insert_sort(int a[], int index[], int n) {
int j;
int temp;
for(int i = 0 ; i < n; i++) {
index[i] = i;
}
for(int i = 1; i < n; i++) {
j = i;
temp = index[i];
while(a[index[j-1]] > a[temp] && j > 0) {
index[j] = index[j-1];
j--;
}
index[j] = temp;
}
}
void re_arrange(int a[], int index[], int n) {
int *p;
p = (int *)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++) {
p[i] = a[index[i]];
}
for(int i = 0; i < n; i++) {
a[i] = p[i];
}
}
int main(int argc, const char * argv[]) {
int length;
int *index;
int *array;
int *sentinel_array;
int *indirect_array;
char *str = "TOLEARNSORTALGORITHM";
length = (int)strlen(str);
array = (int *)malloc(sizeof(int) * length);
index = (int *)malloc(sizeof(int) * length);
indirect_array = (int *)malloc(sizeof(int) * length);
sentinel_array = (int *)malloc(sizeof(int) * (length + 1));
sentinel_array[0] = -1;
for(int i = 0; i < length; i++) {
array[i] = str[i];
index[i] = i;
indirect_array[i] = str[i];
sentinel_array[i+1] = str[i];
}
printf("Before Insert Sort about normal array");
print_array(array, length, 'c');
insert_sort(array, length);
printf("After Insert Sort about normal array");
print_array(array, length, 'c');
printf("Before Insert Sort about sentinel array");
print_array(sentinel_array, length+1, 'b');
sentinel_insert_sort(sentinel_array, length+1);
printf("After Insert Sort about sentinel array");
print_array(sentinel_array, length+1, 'b');
printf("Before Indirect Insert Sort");
printf("Array");
print_array(indirect_array, length, 'i');
printf("Index");
print_array(index, length, 'd');
indirect_insert_sort(indirect_array, index, length);
printf("After Indirect Insert Sort");
printf("Array");
print_array(indirect_array, length, 'i');
printf("Index");
print_array(index, length, 'd');
re_arrange(indirect_array, index, length);
printf("After Re Arrange");
printf("Array");
print_array(indirect_array, length, 'i');
printf("Index");
print_array(index, length, 'd');
return 0;
}실행 결과
