삽입 정렬

• 삽입 정렬(Insertion sort)

  삽입 정렬은(insertion sort)는 정렬된 부분의 위치에 데이터를 삽입하여 정렬하는 알고리즘으로 worst case는 $O({ n }^{ 2 })$이며, best case일때(이미 정렬된 상태)는 $O({ n })$의 성능을 보인다.

---

• 예시)

  1회전 :

  10 6 1 3 4

  10 6 1 3 4

  2회전 :

  10 6 1 3 4

  6 10 1 3 4 -> swap

  6 10 1 3 4

  3회전 :

  6 10 1 3 4

  6 10 1 3 4 -> swap

  6 1 10 3 4

  6 1 10 3 4 -> swap

  1 6 10 3 4

  1 6 10 3 4

  삽입(insert)이 이루어진다고 하지만 사실상 swap이랑 같은 의미이다. 데이터가 5개가 있다고 가정하면 1회전 끝나면 하나에 데이터가 정렬되있으며, 2회전은 2개의 데이터… N회전을 거치면 N개의 데이터가 정렬되게 된다.

---

• 코드 구현(C++)

#include <iostream>
#include <algorithm>
using namespace std;
int A[5] = { 10,6,1,3,4 };
void print_arr() {
	for (int i = 0; i < 5; i++) cout << A[i] << " ";
	cout << "\n";
}
int main(void) {
	print_arr();
	for (int i = 1; i < 5; i++) {
		for (int j = i; j > 0; j--) {
			if (A[j] < A[j - 1]) {
				int temp = A[j];
				A[j] = A[j - 1];
				A[j - 1] = temp;
			}
			else
				break;
		}
		print_arr();
	}
	return 0;
}

---

• 결과