알고리즘: 삽입정렬

삽입정렬

이미 정렬된 범위에 데이터를 적절한 위치에 삽입시켜 정렬하는 방식으로, 시간 복잡도는 O(n^2)이다.

핵심이론

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것

정렬 과정

1. 정렬하려는 값 선택
2. 이미 정렬되어 있는 범위에서 적절한 위치 탐색
3. 탐색이 완료되면 해당 위치까지의 값들을 모두 shift
4. 해당 위치에 데이터를 삽입하고 정렬된 범위를 증가(+1)
5. 정렬된 범위가 전체 리스트의 크기와 동일해질때까지 반복

코드 구현

for i in range(1, n):
    insert_point = i # 현재 인덱스 번호 저장
    insert_value = lst[i] # 현재 값 저장
    for j in range(i-1, -1, -1): # 현재 값 위치의 바로 전 값을 비교하면서 왼쪽으로 이동
        if lst[j] < lst[i]: # 비교대상이 나보다 작으면(해당 위치에 삽입해야함)
            insert_point = j+1 # 나보다 작은 값의 앞에 저장해야하니 +1
            break
        if j == 0: # 끝까지 탐색했을 경우(현재 값이 가장 작은 값일 경우)
            insert_point = 0 # 맨 앞에 삽입
    for j in range(i, insert_point, -1): # i부터 insert_point까지
        lst[j] = lst[j-1] # 값들을 오른쪽으로 한 칸씩 shift
    lst[insert_point] = insert_value # 삽입 위치에 현재 데이터 저장

키 포인트

우선 현재 인덱스 번호와 현재 값을 저장해놔야한다.(그래야 탐색 완료 후 해당 위치에 값을 넣을 수 있기 때문)
그리고 for문의 범위 지정과 종료 조건을 정하는 것이 어려웠다.
위의 코드는 오른쪽부터 왼쪽으로 비교를 했는데, 그러려면 index번호를 하나씩 줄여나가야하기 때문에 step을 -1로 설정했다.
정렬은 for문을 응용할 수 있는 능력을 기를 때 좋은 예제인 것 같다.
삽입 위치를 찾을 때 이진탐색을 이용하면 시간 복잡도를 O(logN)으로 줄일 수 있다