[기본 정렬 알고리즘 #2] 삽입 정렬

📌 기본 정렬 알고리즘

- 버블 정렬
- 삽입 정렬 ✔
- 선택 정렬
- 참고, 공간복잡도

 

1. 삽입 정렬 (insertion sort) 란?

---

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반목, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

https://visualgo.net/en/sorting 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

 

2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것)

---

for index in range(데이터길이 - 1):
  for index2 in range(index + 1, 0, -1):
    if data[index2] < data[index2 - 1]:
      swap(data[index2], data[index2 - 1])
    else:
      break

 

 

3. 알고리즘 구현

---

def insertion_sort(data):
  for index in range(len(data) - 1):
    for index2 in range(index + 1, 0, -1):
      if data[index2] < data[index2 - 1]:
        data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
      else:
        break
  return data

import random

data_list = random.sample(range(100), 50)
print(insertion_sort(data_list))

[0, 2, 4, 7, 9, 10, 12, 13, 14, 16, 17, 19, 21, 22, 23, 28, 33, 34, 35, 39, 40, 42, 50, 52, 55, 57, 58, 59, 60, 61, 64, 67, 70, 71, 74, 75, 76, 78, 79, 81, 84, 86, 87, 89, 90, 92, 95, 97, 98, 99]

 

 

4. 알고리즘 분석

---

• 반복문이 두 개 O(n^2)
  • 최악의 경우, n*n(n-1)/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)