[Python] 삽입 정렬(Insertion sort)

 

삽입 정렬이란?

• 데이터들 중 두 번째 값부터 시작해서 그 앞의 데이터들과 비교해서 알맞은 위치로 삽입하는 형태의 정렬
• 앞 원소보다 크고, 뒤 원소보다 작은 위치에 삽입한다.
• 즉, 선택된 값의 앞쪽 원소들은 이미 정렬되어 있다.

 

 

과정

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

 

Insertion sort

 

 

특징

• 시간 복잡도는 O(N^2)
• 정렬이 어느정도 되어있는 상태에서는 삽입 정렬이 빠르다.
• 배열이 길어질수록 효율이 떨어진다.

 

 

Python code

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

 

 

insertion sort 확인하기

import random

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

 

 

 

 

 

 

 

 

---

Reference

칸아카데미_삽입정렬

위키피디아_삽입정렬