삽입정렬 (insertion sort)

🙇‍♀️삽입정렬 (insertion sort)

🪐삽입정렬 (insertion sort)

기본 정렬 중 가장 많이 쓰이는 정렬 중에 하나이다.
기본 정렬 중 가장 효율이 좋다.

void insertionSort(vector<int>& seq)
{
	int cur;
	for (int i = 1; i < seq.size(); ++i)
	{
		cur = seq[i];
		for (int j = i - 1; j >= 0; --j)
		{
			if (cur < seq[j])
				swap(seq[j + 1], seq[j]);
		}
	}
}

i는 1부터 끝까지 순회를 하면서 i번째 값을 저장한다.
j은 i이전의 수들을 순회하는데 저장된 값과 비교하면서 정렬하게된다.