삽입 정렬 (Insertion Sort)

#Insertion_Sort

" 리스트에 있는 값들을 왼 쪽부터 탐색하면서 정렬되어야 할 위치로 옮겨주자! "

 

#Sudo_code

1. 리스트에 있는 값들 중 맨 왼 쪽에 있는 index 값과 index+1을 한 바로 오른 쪽의 값을 비교해 준다.

2. 만약 index의 값이 index+1의 값 보다 클 경우 해당 값을 서로 swap 해주고, 비교해 줄 index를 줄여준다.

3. 2번 과정을 진행(index가 줄어드는 것)을 통해 index의 왼쪽에 정렬 되었던 값들과 비교를 또 진행해서 왼쪽의 정렬을 완성 해준다.

4. 리스트 길이의 -1만큼 위 과정을 진행한다. 그 이유는 해당 과정이 진행 될 때 비교할 index를 기준으로 왼쪽에는 정렬된 리스트이기 때문에 이미 비교를 진행했기 때문이다.(설명 부족 ㅠ 느낌만 이해)

 

#Code

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <stdio.h>   int main(){     int i, j, temp;     int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};       for(int i = 0; i < 9; i++)     {         j = i;         while(j > 0 && array[j] > array[j+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; } Colored by Color Scripter

cs

 

 

 

 

#Feature

삽입 정렬은 데이터가 이미 정렬된 상태에서 빠른 특징이 있다!!

 

#Time

시간 복잡도 = O(N^2)