insertion sort (1) 썸네일형 리스트형 30. Insertion Sort 삽입 정렬(Insertion Sort)은 각각의 원소를 이전에 정렬한 앞쪽 원소들과 비교해서 맞는 위치에 추가하는 과정을 반복한다. 원소를 앞쪽에 추가하면 이전에 정렬된 원소 중 이번 원소가 추가될 자리 뒤쪽에 있는 원소들의 위치가 하나씩 뒤로 밀리게 되므로 단순히 각각의 원소를 바로 앞 원소부터 차례로 비교하면서 비교 관계가 바뀌었다면 서로 바꾸는 식으로 구현하면 된다. 다음은 이전 글에 예시로 나온 정렬을 C++에서 삽입 정렬로 구현한 코드이다. for(k = 0; k++ 1 && a[i - 1] > a[i]; i--)swap(a[i - 1], a[i]); } 이 코드는 굉장히 간단하고, 시간복잡도가 $O(n^2)$이라서 앞의 두 코드보다 약간 더 빠른 경우가.. 이전 1 다음
