Insertion Sort

기본 아이디어

정렬 중간 과정에 데이터가 왼쪽 데이터와 오른쪽 데이터로 나뉘어 진다.
왼쪽 데이터는 정렬이 된 데이터가 있고 오른쪽 데이터는 정렬이 되지 않은 데이터가 있다.
오른쪽 데이터는 제일 앞 숫자를 왼쪽에 정렬된 데이터의 제 위치에 삽입한다.
삽입하는 과정에서 삽입될 위치와 원레 위치 중간의 모든 데이터는 오른쪽으로 한 칸씩 이동한다.

구현

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
void swap(int& i, int& j) {
	int k;
	k = i;
	i = j;
	j = k;
}

void InsertionSort(vector<int>& A) {
	int n = A.size();

	for (int i = 1; i < n; i++) {
		for (int j = i; j > 0 && A[j - 1] > A[j]; j--) {
			swap(A[j-1], A[j]);
		}
	}
}

void print(vector<int> A) {
	for (auto el : A) {
		cout << el << " ";
	}
	cout << endl;
}
void main() {
	vector<int> A = { 9,6,3,1,2,4,5,7,8 };
	print(A);
	InsertionSort(A);
	print(A);
}

실행 과정

1. 시작 : 첫 번쨰 원소는 이미 정렬된 부분 리스트로 간주된다.
2. 원소 선택 : 정렬되지 않은 부분의 첫 번쨰 원소를 선택한다.
3. 정렬된 부분 리스트 내 탐색 : 현재 선택한 원소보다 큰 원소를 만나면 그 원소를 오른쪽으로 한 칸씩 이동시킵니다. 이과정을 반복한다.
4. 원소 삽입 : 현재 원소를 올바른 위치에 삽입한다.
5. 반복 : 정렬되지 않은 부분에 원소가 남아 있지 않을 떄까지 위의 과정을 반복한다.