Py) 삽입정렬 Insertion Sort

• 정렬되어 있는 리스트에 새로운 값을 적절한 위치에 삽입하는 과정 반복
• 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하는 것으로 생각
• 안정된 정렬, 데이터 수가 적을 경우와 이미 정렬되어 있는 경우 유리
• 복잡도 분석:
  • 삽입정렬 외부루프 n-1번 실행, 각 단계에서 1번의 비교와 2번의 이동이 이루어짐. 총 비교횟수 n-1번, 총 이동횟수 2(n-1)번. 따라서 최선의 경우 O(n)
  • 입력 자료가 역순일 경우는 최악의 경우. 전부 한 칸씩 이동 O(n^2)

 

알고리즘

1. 인덱스 0은 이미 정렬되었다고 생각, 인덱스 1부터 시작
2. 현재 정렬된 배열은 i-1까지 이므로 j(삽입하고자 하는 원소 위치)를 i-1부터 역순으로 진행
3. j가 왼쪽 원소보다 작을 경우 swap

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

#왼쪽으로 이동하면서 바꿔준다
for i in range(1, len(array)): #인덱스 0은 이미 정렬되었다고 생각, 인덱스 1부터
    for j in range(i, 0, -1): #range -> i 부터 1까지 1씩 감소하며 진행
        #j는 삽입하고자 하는 원소의 위치
        #한칸씩 왼쪽으로
        if array[j] < array[j-1]:
            array[j],array[j-1] = array[j-1], array[j]
        #j가 그 왼쪽 원소보다 크거나 같으면 정지
        else:
            break
print(array)