정렬 알고리즘(C++) / 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬 애니메이션

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

k번째 반복 후의 결과 배열은 앞쪽 k+1 항목이 정렬된 상태이다. 

두번째 인덱스부터 시작하여 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

선택 정렬과 유사하지만 더 효율적인 정렬 알고리즘이다. 

 

시간 복잡도 & 공간 복잡도

• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(n) 

최선의 경우 O(n)이라는 시간 복잡도를 가지지만 최악의 기준으로는 O(n^2)의 복잡도를 가진다. 최선의 경우는 대부분의 원소가 이미 정렬되어 있는 경우를 말한다. 

안정 정렬이다. 

버블 정렬이나 선택 정렬과 같은 시간 복잡도를 가지지만 보다 빠르다. 

 

코드(C++) - 백준 2750

//2750 삽입정렬
#include<iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	int arr[1001];
	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		arr[i] = num;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[i]) {
				int temp = arr[i];
                //뒤로 한칸씩 밀어주기
				for(int k = i; k > j; k--) {
					arr[k] = arr[k - 1];
				}
				arr[j] = temp; //삽입
			}
		}
	}

	//출력
	for (int i = 0; i < N; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

삽입 정렬 알고리즘

 

참고 - 위키 백과

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전