이코테-chapter6: 삽입 정렬

정리 내용

삽입 정렬

• inserting sort의 약자.
• 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.
• 데이터가 거의 정렬되어 있을 때 효율적이다.
• 특정한 데이터를 적절한 위치에 삽입한다는 의미이다.
• 삽입 정렬은 두 번째 데이터부터 시작하며 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단한다.
• 특정 데이터를 적절한 위치에 삽입하는데 그 앞까자의 데이터는 이미 정렬되어 있다고 가정한다.
• 시간 복잡도 O(N^2)
• 정렬의 거의 되어 있는 최선의 경우 퀵 정렬 보다 더 빠른 O(N)을 가진다.

삽입 정렬 소스코드

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

for i in range(1, len(array)):
    for j in range(i, 0, -1):  # 인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j-1]:  # 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:   # 자기보다 작은 데이터를 만나면 그 자리에서 break
            break

print(array)

출처 && 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github