[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬: 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결

무조건 위치를 바꾸는 게 아니라 필요 시에만 위치를 바꿔서 정렬함

 

삽입 정렬의 시간 복잡도: O(N^2)

 

<1 10 5 8 7 6 4 3 2 9 >숫자들을 오름차순으로 정렬하는 코드는 아래와 같다. 

코드: 

#include <iostream>
#include <string>
#include <algorithm>
#include<vector>
#include <queue>
#include <cmath>

using namespace std;
// 삽입 정렬은 필요할 때만 위치를 바꾸게 됨
// 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결함

int main(void) {
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

	for (i = 0; i < 9; i++) {
		j = i;
		while (array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for (i = 0; i < 10; i++)
		cout << array[i] << ' ';

	return 0;
}

https://youtu.be/16I9Z7bS1iM?si=8f0U8H7FM-ki4MVJ

해당 포스팅은 나동빈님의 실전 알고리즘 강좌를 보고 정리하였다.