[알고리즘] 삽입정렬

목표

• 기초적인 정렬 알고리즘 중 삽입 정렬 알고리즘에 대해 이해한다.
• 기초적인 장렬 알고리즘 중 삽입 정렬 알고리즘을 c++로 구현한다.

삽입 정렬 알고리즘이란?

• 삽입 정렬 알고리즘은 정렬된 위치에 삽입한다 하여 삽입 정렬 알고리즘이다.
• 자료 배열의 모든 요소를 정렬된 배열 부분과 비교하여. 자신의 위치에 삽입하는 알고리즘이다.
• 쉽게 일상에서 손안의 카드를 정렬하는 방법과 유사하다.

삽입 정렬 알고리즘의 예

• 31 8 45 73 3

삽입 정렬 알고리즘의 특징

• 배열의 모든 요소가 대부분 정렬되어 있는 경우 아주 효율적!
• 입력자료가 역순인 경우 최악의 경우로 n^2의 시간 복잡도를 가진다.

삽입 정렬 알고리즘의 구현

#include <iostream>
using namespace std;
int main (){
	int i, j, temp;
	int ary[5] = {31, 8, 45, 73, 3};
 	for(int i = 1; i < 5; i++){
 		j = i;
 		while(ary[j-1] > ary[j]){
 			temp = ary[j-1];
 			ary[j-1] = ary[j];
 			ary[j] = temp;
 			j--;
		 }
	}
	for(int i = 0 ; i < 5 ; i ++)
		cout << ary[i] << ' ';
}

 

정리 및 느낀 점

• 삽입정렬 알고리즘 경우 자료가 어느 정도 정렬이 되어있다면 최고의 효율을 가진다.
• 최악의 경우는 선택, 버블 정렬 알고리즘과 같은 시간 복잡도인 n^2 을 가진다.

참조

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=5