[알고리즘] 삽입 정렬

[삽입 정렬]

• 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
• 버블 정렬은 큰숫자를 뒤로 밀어내며 정렬하는 반면, 삽입 정렬은 정렬이 이미 되어있는 앞부분과 나 자신을 비교해서, 나 자신이 어디에 삽입되면 되는지를 찾는다.
• 데이터가 거의 정렬되어있다면 매우 효율적인 알고리즘이다.
• 정렬되어 있는 배열과 비교할 때도, 자기보다 작은 데이터를 만나면 그 위치에서 멈추면 되므로 모든 데이터를 다 볼 필요가 없다.
• 시간 복잡도는 \( O(N^2) \) 이며, 최선의 경우 \( O(N) \) 을 갖는다.

---

빨간 박스는 이미 정렬되어 있는 부분을 말한다.

1. 처음에는 자료에서 두 번째 요소를 가지고 이전 데이터와 비교를 시작하며 빨간색 박스를 찾는다.

2. 정렬되어있지 않은 값을 하나하나 정렬된 배열(빨간색 박스)에 삽입해나간다.

3. 자료의 마지막 요소까지 삽입을 다 하고 나면 정렬이 끝난다.

---

• 삽입 정렬을 코드로 구현해봅시다.

코드 참조; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.

def insert_sort(datas):
    for i in range(1,len(datas)):    # 0번째 요소는 뒤에 요소가 없으므로 1부터 시작합니다.
        for j in range(i,0,-1):      # 자기 자신과 이전 요소를 비교해가며, 이전 요소가 0이 될때 까지 비교합니다.
            if datas[j] < datas[j-1]:
                datas[j], datas[j-1] = datas[j-1],datas[j]
                print(datas)

datas = [5, 10, 2, 1, 0]
insert_sort(datas)

'''
[5, 2, 10, 1, 0]
[2, 5, 10, 1, 0]
[2, 5, 1, 10, 0]
[2, 1, 5, 10, 0]
[1, 2, 5, 10, 0]
[1, 2, 5, 0, 10]
[1, 2, 0, 5, 10]
[1, 0, 2, 5, 10]
[0, 1, 2, 5, 10]
'''

---

[실습1] 1부터 1000까지 난수 100개를 생성하고, 다음의 요구사항을 만족시키는 프로그램을 구현하여 보자.

1) 생성된 난수들을 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현

2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현

import random

def insert_sort(seq):
    for i in range(1,len(seq)):
        for j in range(i,0,-1):
            if seq[j] < seq[j-1]:
                seq[j],seq[j-1] = seq[j-1], seq[j]
            else : break

randomlist = [random.choice(range(1,1001)) for i in range(100)]
insert_sort(randomlist)
print(f'정렬된 난수들 : {randomlist}')
print(f'최댓값 : {randomlist[-1]}')
print(f'최솟값 : {randomlist[0]}')