[정렬 알고리즘] Insertion Sort(삽입정렬)

§Insertion Sort

손에 카드를 정렬 하는 것처럼 하나의 카드씩 제자리로 정렬하는 알고리즘이다.

 

1. 현재 위치 k원소를 (k-1)부터 1까지 원소와 비교하며 자리를 바꾸어 나간다.
2. 1 부터 n-1까지 위 행위를 반복한다.

 

&example

Time Complexity: O(n2) as there are two nested loops. 

코드( C )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

//////////////////////////////// //    Insertion Sort //    삽입 정렬 ////////////////////////////////     #include <stdio.h>   void insertionSort(int arr[], int n) {     int i, key, j;     for (i = 1; i < n; i++) {         key = arr[i];         j = i - 1;           while (j >= 0 && arr[j] > key) {             arr[j + 1] = arr[j];             j = j - 1;         }         arr[j + 1] = key;     } }   void printArray(int arr[], int size) {     int i;     for (i = 0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }   int main() {     int i, j, arr[] = { 12,11,13,5,6 };     int n = sizeof(arr) / sizeof(arr[0]);       insertionSort(arr, n);     printf("Sorted Array : ");     printArray(arr, n);     return 0; }   Colored by Color Scripter

cs