[C code] 삽입 정렬 (Insertion sort)

#include <stdio.h>
#include <stdlib.h>

// Function to sort an array using insertion sort
void InsertionSort(int arr[], int n)
{
    int key, i, j;

    for(i=0 ; i<n ; i++)
    {
        j = i-1;
        key = arr[i];

        while(j>=0 && arr[j]>key)
        {
            arr[j+1] = arr[j];
            j--;
        }

        arr[j+1] = key;
    }
}

/* Function to print an array */
void PrintArray(int arr[], int size)
{
   printf("\n**********************\n");
   for(int i=0 ; i<size ; i++)
   {
       printf("%4d", arr[i]);
   }
}

// Driver program to test above functions
int main()
{
    int array[5];

    for(int i=0 ; i<5 ; i++)
    {
        printf("Put your %d integers : ", i);
        scanf("%d", array+i);
    }

    PrintArray(array, sizeof(array)/sizeof(array[0]));
    InsertionSort(array, sizeof(array)/sizeof(array[0]));
    PrintArray(array, sizeof(array)/sizeof(array[0]));

    return 0;
}

삽입정렬은 우리가 손으로 가드게임을 하듯이 작동하는 간단한 정렬방법이다

- 최악 : O(n^2) / 최선 : O(n) / Stable Sort

Example:

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12

11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13

11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.

5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.

5, 6, 11, 12, 13

​

- GeeksforGeeks