[정렬] 3.삽입 정렬

삽입 정렬

- 이미 정렬된 부분은 항상 정렬되어 있다.

- 처음에는 정렬된 부분에 원소가 1개

- 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다.

 

시간 복잡도 Θ(n^2)

- 가장 좋을 때: 이미 오름차순으로 정렬되어 있을 때 -> 총 n-1 번 = Θ(n)

- 최악의 경우: 역순으로 정렬되어 있을 때

i번째 위치의 원소를 정렬된 부분에 추가할 때, i-1 개의 원소와 모두 비교해야한다.

i = 2,3, ..., n일 때 각각 비교해야할 개수는 1+ 2+ ... + n-1 = n(n-1)/2 = Θ(n^2)

 

 

삽입 정렬 Python 코드

def insertionSort():
    nums = list(map(int, input().split(' ')))
    
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            if(nums[j-1] > nums[j]):
                nums[j-1], nums[j] = nums[j], nums[j-1]

    print(nums)

입력 및 출력 결과