삽입 정렬(Insort Sort)

카드를 순서대로 정리하는 모습과 비슷하다. 

요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 작업을 반복한다.

1. 데이터 집합에서 정렬 대상이 되는 요소들을 선택한다.

2. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다.

3. 2번과정에서의 요소를 왼쪽에 자신보다 큰 값이 없는 장소에 삽입한다.

4. 정렬이 완료될때까지 1~3번 과정을 반복한다.

소스코드

#include <iostream>
 
using namespace std;
 
void insert_sort(int *arr , int len)
{
    int tmp;
    
    for(int i = 1 ; i<len;i++)
    {
        tmp = arr[i];
        for(int j = i - 1 ; j>=0 ; j--)
        {
            if(arr[j]>tmp)
            {
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}
 
int main()
{
    int arr[5] = {2,1,9,6,5};
 
    insert_sort(arr,5);
    for(int k = 0 ;k<5 ; k++)
            cout<<arr[k]<<" ";
 
        cout<<endl;
 
    return 0;
}