삽입 정렬 Insertion Sort

삽입 정렬 알고리즘

순서가 틀린 아이를 꺼내서 위치에 맞게 넣는 것

• 예시

삽입 정렬 함수 구현

def insertion_sort(array):
    for index in range(1, len(array)):
        position = index # 삽입정렬은 처음에 인덱스를 다른 변수에 저장
        temp_value = array[index]

        while position > 0 and array[position-1] > temp_value:
            array[position] = array[position-1]
            position = position -1

        array[position] = temp_value
    return array

• position = index

  temp_value = array[index]

  : 필요한 변수를 만들어주는 부분

• for index in range(1, len(array)):

  index 가 1부터 시작한다는 점이 중요 ~ n-1

• while position > 0 and array[position-1] > temp_value:

  : 패스스루를 통해서 옆으로 이동하는 부분

삽입 정렬의 효율성

삽입 정렬은 삭제, 비교, 시프트, 삽입 단계로 구성

비교 횟수

• 공백 왼쪽에 있는 값과 temp_value를 비교할 때마다 실행
• 최악의 경우 : 배열이 역순으로 정렬된 경우
• 총 비교 횟수 : 1 + 2 + ... + N-1

시프트 횟수