[Algorithms] 단순 삽입 정렬(Straight Insertion Sort)

깃허브: https://github.com/PSLeon24/DataStructure/blob/main/Sorting%20algorithm.ipynb

기본 정렬(Sorting algorithms)

기본 정렬의 종류

선택 정렬, 버블 정렬, 삽입 정렬

- 선택 정렬(더보기: https://psleon.tistory.com/30)

- 버블 정렬(더보기: https://psleon.tistory.com/31)

본 포스팅에서는 단순 삽입 정렬을 다루고자 함

 

단순 삽입 정렬(Straight Insertion Sort, Shuttle Sort)

단순 삽입 정렬은 단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하는 것이 아니라는 차이점이 있음

단순 삽입 정렬: 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘, 셔틀 정렬(shuttle sort)이라고도 함

위 그림을 예로 들면,

정렬되지 않은 리스트 [6, 5, 3, 1, 8, 7 ,2, 4] 가 있음

step1.

첫 번째 원소는 미리 고정시켜두고, 두 번째 원소인 5부터 주목하여 진행해야 함(즉, index 1번부터 시작)

5는 6보다 앞쪽에 위치해야 하므로 맨 앞에 삽입, 그 후 6은 오른쪽으로 옮겨짐

[5, 6, 3, 1, 8, 7, 2, 4]

step2.

다음으로 세 번째 원소인 3에 주목, 3은 5보다 앞쪽에 위치해야 하므로 맨 앞에 삽입, 이 상태에서 5와 6을 오른쪽으로 옮김

[3, 5, 6, 1, 8, 7, 2, 4]

 

이후 step에서도 위와 같은 작업을 반복해서 수행하여 정렬된 부분과 정렬되지 않은 부분에서 다시 배열을 구성할 경우 '아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입'하는 작업을 n-1번 반복하면 정렬이 완료됨

 

파이썬 실습

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적(stable)

 

단순 삽입 정렬 알고리즘의 시간 복잡도

기본 정렬(선택, 버블, 삽입) 알고리즘의 시간 복잡도는 모두 O(n²)으로 프로그램 효율이 좋지 않음

그 중 이번에 학습한 단순 삽입 정렬은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교·교환 비용이 커지는데, 이를 개선하기 위해 이진 검색법을 사용해 삽입 정렬을 하면, 이미 정렬이 끝난 배열을 제외하고 원소를 삽입할 위치를 검사하므로 비용을 줄일 수 있음

이렇게 '이진 검색법'을 사용해 단순 삽입 정렬을 개선한 알고리즘을 이진 삽입 정렬(binary insertion sort)라고 함