Insertion Sort1 [정렬] 삽입정렬(Insertion Sort) 특징 구현이 간단하다 제자리 정렬이다 안정 정렬이다. 시간 복잡도가 O(n^2)으로 느리다. 기본 아이디어 i는 1부터 시작하여 n-1까지 늘려간다. array[0]부터 array[i-1]까지 정렬되어 있을 때, array[i]를 포함하여 정렬한다. array[i]를 뒤에서부터 순차적으로 array[i-1], array[i-2] ... 과 비교하다가 자기보다 작은 숫자가 나오면 그 뒤에 삽입한다. 아래 영상 참고 www.youtube.com/watch?v=OGzPmgsI-pQ 비교연산은 1 + 2 + 3 + ... + (n-1) 회 일어나고, 스왑 연산의 횟수도 비교 연산과 같으므로 시간 복잡도는 O(n^2) 파이썬 코드 def insertion_sort(array): for i in range(1, l.. 2021. 3. 28. 이전 1 다음