[알고리즘] 삽입 정렬(Insertion Sort) 구현 (C++)

삽입 정렬이란

 

두 번째 원소부터 그 앞의 원소들과 차례로 비교해가며 위치를 옮겨가는 정렬이다. 

 

 

삽입 정렬 진행 순서

 

삽입 정렬의 특징

 

• 하나의 배열 내에서 위치변경만 일어나므로 공간복잡도는 O(1) 
• in-place 정렬이다
• 시간복잡도는 평균 O(n^2) 최악 O(n^2)
• 키 값이 같을 경우에도 정렬 후에 순서가 유지되므로 stable정렬이다
• 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다

 

 

 

구현 (C++)

 

#include <iostream>


using namespace std;
#define listLength 5


void Insertion_sort(int list[])
{
    int key;
    for (int i = 1; i < listLength; i++)
    {
        key = list[i];			//키 값은 list[1]부터 제공
     
    	for (int j = i - 1; j >= 0; j--)
        {
            if(list[j] > key)		// 위치 변경
            {   
                list[j + 1] = list[j];
                list[j] = key;
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int list[] = { 8,25,3,1,4 };

    cout << "--- 리스트 ---" << "\n";
    for (int i = 0; i < listLength; i++)
        cout << list[i] << " ";

	cout << "\n";
    	cout << "\n";

    Insertion_sort(list);		// 삽입 정렬 함수 호출


	cout << "--- 삽입 정렬 후 ---" << "\n";
    for (int i = 0; i < listLength; i++)
        cout << list[i] << " ";

}

 

 

출력