[알고리즘] 삽입정렬

알고리즘

 

삽입정렬(insertion sort)

 

 

 

 

 

간단 요약

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

 

1.  Array[1] 을 key 로 지정한다.

 

2. Array[0] 가 key보다 크면 오른쪽 쉬프트 , key보다 작으면 Array[0] 앞에 key를 삽입.

 

3. key의 인덱스를 하나씩 증가시키며 반복.

 

상세 설명

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

 

 

 

 가장 먼저 두번째 데이터를 key 로 지정한다.

그리고 가장 인접한 데이터 부터 비교하여 이전 데이터가 key 값 보다 큰경우 오른쪽으로 이동

key 값 보다 작은 경우 이전 데이터 앞에 key 삽입

 

 

 

 

 

첫번째 데이터가 key 값보다 크기 때문에 첫번째 데이터를 오른쪽으로 한번 이동

그 후 더 이상 비교할 데이터가 없으므로 첫번째 위치에 key 삽입

다시 key 값을 다음 인덱스로 지정후 비교

 

 

 

 

두번째 값이 key 보다 크므로 이동

첫번째 값이 key 보다 크므로 이동

더 이상 이전 값이 없으므로 첫번째 위치에 key 삽입

 

 

 

네번째 데이터를 key 값으로 지정

두번째 데이터까지 key 값 보다 크므로 모두 오른쪽으로 이동

하지만

첫번째 값은 key 값 보다 작으므로 두번째 위치에 key 삽입

 

 

 

 

 

이 과정을 n번 반복하면 오름차순이 완성된다

 

 

 

 

 

 

시간복잡도

 

코드 

 

#include <iostream>
 
using namespace std;
 
void sort(int * arr)
{
    int i, j;
    int key;
 
    for (i = 1; i < 5; i++) { //key 를 잡아주는 for 문
        key = arr[i];
 
        for (j = i - 1; j >= 0; j--) { // 키 왼쪽 값들을 잡아줌
 
            if (arr[j] > key) { // 왼쪽값이 키보다 작으면 왼쪽값을 오른쪽으로 이동
                arr[j + 1] = arr[j];
            }
            else {
                break; // 왼쪽값이 키보다 작을 경우 break
            }
        }
        arr[j + 1] = key; // 왼쪽값이 작았던 위치에 키를 넣는다
    }
}
 
int main(void)
{
    int arr[5] = { 15, 11, 1, 3, 8 };
    int i;
 
    for (i = 0; i < 5; i++) {
 
        cout << arr[i] << endl;
    }
    cout << "\n";
    sort(arr);
    for (i = 0; i < 5; i++) {
        cout << arr[i];
    }
 
    return 0;
 
}
 

 

출처 : https://terms.naver.com/entry.nhn?docId=2270436&cid=51173&categoryId=51173

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html