[알고리즘]정렬-삽입 정렬(Insertion Sort)
삽입 정렬(Insertion Sort) 정렬 알고리즘 3번째 시간입니다.삽입 정렬은 입력 상태에 따라 수행 시간이 달라지는 정렬입니다.삽입 정렬의 최선의 경우, 즉 입력이 이미 정렬되어있는 경우는 시간복잡도가 O(n)으로 굉장히 빠릅니다.거의 정렬된 상태에서는 다른 정렬 알고리즘보다 확실히 빨라집니다.반면에 역으로 정렬된 입력에 대해서는 O(n^2)의 시간이 걸립니다. 삽입 정렬 컨셉 배열을 정렬된 부분(앞 부분)과 아직 정렬 안 된 부분(뒷 부분)으로 나누어,정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분에서 정렬되게 위치시키는 작업을 합니다.이 작업을 정렬 안 된 부분이 없어질 때까지 반복합니다. 예시 입니다. 코드123456789101112131415161718192021def Insertion_..
2017. 1. 22. 02:40