Python - 삽입정렬

삽입정렬

삽입정렬은 손에 들고있는 카드정렬과 비슷하다. 정렬할 카드를 각 카드와 비교해서 사이에 두는 방식이다.

 

예제

nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)):
    i2 = i1 -1
    currentNum = nums[i1]

    while nums[i2] > currentNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 + 1] = currentNum

print(nums)

 

내용

삽입정렬의 첫 시작은 두번째 값부터 시작한다. 앞의 값은 정렬이 되어 있다고 가정하기 때문이다.

 i1은 정렬을 수행할 값의 인덱스를 저장하고, i2는 정렬을 수행할 현재값의 앞 인덱스를 저장한다.

 while문을 이용하여 정렬된 앞의 값들과 차례대로 비교한다.

 앞의 값과 비교하여 현재값이 작다면 두 값을 바꿔주고 i2(정렬을 수행 할 현재값 앞 인덱스)가 앞으로 바뀌었기 때문에 -1 해준다.

 계속 비교하여 큰 값을 뒤로 밀어내고 인덱스 0까지 비교하거나 현재값보다 작은값이라면, while문을 빠져나와 해당 인덱스에 현재값을 삽입한다.

 

while문의 부등호를 <로 변경하면 내림차순으로 정렬된다.

 

결과

[0, 1, 2, 5, 10]