삽입정렬1 삽입정렬(Insertion Sort) 개념/시간복잡도/Stable/In-place 삽입정렬에 대한 이해 - 삽입정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다. - 새로운 원소를 올바른 위치에 삽입시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다. N = 8인 다음과 같은 수열을 오름차순으로 정렬해보자. 0번째 인덱스에 있는 수는 그 자체로 정렬이 되어있으므로 그 다음 인덱스인 1번 인덱스 부터 올바른 위치에 삽입을 시작한다. 인덱스 1번 이전에 있는 수와 1번을 비교했을 때, 인덱스 0번에 있는 수 3은 인덱스 1번에 있는 수 7보다 작으므로 자리 교환없이 삽입을 끝낸다. 이후, 인덱스 2번에 있는 수를 이전까지 정렬된 수열 [3, 7] 에 삽입한다. 인덱스 2번 이전에 있는 수들과 2번을 비교했을 때, 인덱스 1번에 있는 수 7은 인.. 2022. 2. 11. 이전 1 다음