삽입 정렬1 [Python]Insertion Sorting 삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다. 장점은 N의 크기가 작을때 효과적이라는 것 단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2) 정리 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx def insertion_sort(a): n = len(a) for i in range(n): for j in range(i-1, -1, -1): if a[i] < a[j]: a[i], a[j] = a[j], a[i] i = j 2019. 5. 10. 이전 1 다음 728x90 반응형