[알고리즘] 삽입 정렬(揷入整列, insertion sort)

 

 

 

 

 

알고리즘 개요 및 소개

Insertion Sort Animation

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도	O(N^2)
장점	거의 정렬된 상태에서 가장 효율이 좋다. N^2 알고리즘 중에서 가장 빠르다. 구현이 간단하다
단점	배열이 길어질수록 효율이 떨어진다.

소스코드

#include<iostream>
constexpr int MAX_LIST = 10;

/*
Insertiopn Sort 알고리즘의 핵심은 각 숫자를 적절한 위치에 삽입하면 어떨까?
*/
int main() {

	int list[MAX_LIST] = { 26,5,37,1,61,11,59,15,48,19 };
	int temp;
	int max = MAX_LIST;

	for (int i = 0; i < MAX_LIST-1; ++i) {
		//왼쪽은 항상 자기보다 작은 수 이다.
		
		for (int j = i; j >=0; --j) {

			if (list[j] > list[j + 1]) {
				temp = list[j];
				list[j] = list[j + 1];
				list[j + 1] = temp;

			}
		}
	}

	std::cout << "Sort Result: ";
	for (auto i : list) {
		std::cout << i << " ";
	}
	std::cout << std::endl;
	system("pause");
}

 

후기

선택 정렬, 버블 정렬, 와 3대의 N^2 알고리즘을 구현해보았다. 3개 알고리즘 다 비슷해서 헷갈린다.

쉬운 정렬 알고리즘은 삽입 정렬까지 이며 쉬운만큼 속도가 느려서 현업에서는 많이 사용하지 않는 걸로 알고 있다. 이다음부터는 퀵 정렬을 할 예정이다.

 

 

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/삽입_정렬

Blog: https://blog.naver.com/ndb796/221226806398