삽입 정렬(Insertion Sort)

전개

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
내용 출처

1. 주어진 배열의 1번째부터 n번째까지 차례대로 원소를 꺼낸다.
2. 꺼낸 원소의 값과, 원소의 이전 위치의 값들을 차례대로 비교한다.(n-1번째부터 0번째까지)
3. 원소 값보다 비교하는 값이 더 클 경우, 비교하는 값을 오른쪽으로 한 칸 이동시키고 비교할 인덱스의 값을 하나 감소시킨다. (더 큰 값을 오른쪽으로 한 칸 이동시키는 이유는 그 앞에 삽입할 공간을 만들어주기 위함이다.)
4. 위의 과정을 계속 반복하다가 비교할 인덱스가 0보다 작아지거나, 비교하는 원소가 기존 원소와 같거나 작아지면 반복을 마친다.
5. 반복문을 마친 인덱스 다음 위치에 처음 (꺼낸) 원소를 저장한다. (반복문을 마친 인덱스의 값이 꺼낸 원소와 같거나 작기 때문에 다음 인덱스에 저장한다.)

시간 복잡도

• O(${N^2}$)

구현 코드

def insertion_sort(numbers):
    """ 오름차순 삽입 정렬을 실행합니다. """
    n = len(numbers)

    for i in range(1, n):
        now = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > now:
            numbers[j + 1] = numbers[j]
            j -= 1
        numbers[j + 1] = now


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]

    insertion_sort(numbers)

    print(numbers)


'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
'''

Ref

• 모두의 알고리즘 with 파이썬