이번 시간에는 삽입정렬에 대해서 알아보겠다.
삽입정렬이란?
-
손안의 카드를 정렬하는 방법과 유사하다.
- 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
- 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
-
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
-
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다
삽입 정렬(insertion sort) 알고리즘의 구체적인 개념
-
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
-
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
처음 Key 값은 두 번째 자료부터 시작한다
삽입 정렬(insertion sort) 알고리즘의 예제
코드[1]
// 삽입 정렬
void insertion_sort(int list[], int n){
int i, j, key;
// 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
for(i=1; i<n; i++){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 되고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for(j=i-1; j>=0 && list[j]>key; j--){
list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j+1] = key;
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {8, 5, 6, 2, 4};
// 삽입 정렬 수행
insertion_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}코드[2] - 동빈나 강의
#include <stdio.h>
int main()
{
int i, j, temp;
int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2};
for (int i = 0; i < 9; i++)
{
j = i;
while (array[j] > array[i + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
j--;
}
}
for (int i = 0; i < 10; i++)
{
printf("%d", array[i]);
}
return 0;
}
//개념 [삽입정렬]
//흔히 말해서 1 3 7 5 9 4 10 2 가 있다고 가정하자.
// 왼쪽수를 기준으로 왼쪽과 오른쪽을 비교하고 왼쪽이 더 크다면 자리를 바꾸는 아이디어다.
// swap한다.
// 반복문을 돌리기 떄문에 시간복잡도는 O(n^2)이다.
// 구현은 어떻게 하나?
//[구현]
//key point
// 1. 배열 선언 = {값 섞여있다.}
// for문을 { 안에 while문[array[i]>arrasy[j] { } }으로 구성
// while문은 돌리면서 swap을 진행
// swap을 진행하면서[비교하면서 값을 change]
// j-- 감소시킨다.
삽입 정렬(insertion sort) 알고리즘의 특징
장점
안정한 정렬 방법
레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
단점
비교적 많은 레코드들의 이동을 포함한다.
레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.
삽입 정렬(insertion sort)의 시간복잡도
최선의 경우
비교 횟수
이동 없이 1번의 비교만 이루어진다.
외부 루프: (n-1)번
Best T(n) = O(n)
최악의 경우(입력 자료가 역순일 경우)
비교 횟수
외부 루프 안의 각 반복마다 i번의 비교 수행
외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
교환 횟수
외부 루프의 각 단계마다 (i+2)번의 이동 발생
n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)
Worst T(n) = O(n^2)
정렬 알고리즘 시간
출처 |
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
