정렬이란
정렬이란 데이터를 특정한 기준에 따라서 순서대로 정렬하는 것이다.
우리가 흔히 말하는 버블정렬이나, 퀵정렬, 선택정렬에서 들어본 정렬이
이에 속한다.
데이터를 정렬하면 이진탐색이 가능해진다. 이진탐색을 하기 위해서는 정렬과정이
필수이기 때문이다.
정렬 알고리즘 시각화 사이트
시각화 사이트 이 곳을 클릭하면,
각 정렬 알고리즘이 어떻게 동작하는지 눈으로 확인할 수 있다.
✏️삽입정렬
삽입정렬은 '데이터를 하나씩 확인하여, 각 데이터를 적절한 위치에 삽입하는' 알고리즘이다.
손에 카드를 들고 있다고 생각하면 그 예가 쉽게 이해가 간다.
카드를 보고 적절한 위치를 찾아 삽입하는 것처럼, 특정한 데이터를 적절한 위치에 삽입하는 것이다.
삽입 정렬은 선택정렬에 비해 구현 난이돈는 높지만, 선택 정렬에 비해 빠르며 필요할 경우에만 위치를 바꾸기 때문에 효율적인 알고리즘이다. 이렇듯 데이터가 거의 정렬되어 있을 경우에는 더더욱 빠르다.
7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 | 순으로 있을 때,
삽입 정렬은 두 번째 데이터부터 시작한다.
5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
두 번째 카드인 '5'가 어떤 위치로 들어갈지 판단한다. 7보다 작으니 7의 앞인 왼쪽에 삽입한다.
그 다음 세 번째 카드인 '9'가 어떤 위치에 들어갈지 선택하는데, 5와 9보다 크니 그대로 둔다.
0 | 5 | 7 | 9 | 3 | 1 | 6 | 2 | 4 | 8 |
4번째 자리인 '0'을 어떤 위치에 들어갈지 판단하는데, 5, 7, 9보다 작으니 첫번째 위치에 삽입한다.
--중략--
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
이러한 과정으로 삽입 정렬은 두 번째 카드부터 마지막 카드까지 위치를 선택 후, 삽입하는 과정으로 진행한다.
📝삽입정렬 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): #d인덱스 i부터 1까지 감소하며 반복
if array[j] < array[j - 1]
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array)🕝삽입정렬 시간 복잡도
삽입정렬의 시간 복잡도는 for문 안에 또 다른 for문이 있는 형태로, O(N^2)이다.
이는 선택정렬과 마찬가지가 아닌가? 라고 생각될 수 있지만, 삽입정렬의 설명에서 적었듯
선택정렬보다는 빠른 정렬이며, 이미 정렬되어 있을수록 자리를 바꿀 필요가 없기 때문에
매우 빠르게 동작한다.
최선의 경우에는 O(N)의 시간 복잡도를 가질 정도로 매우 빠르게 동작할 수 있다.
해당 포스팅의 개념, 코드, 이미지는 밑 책을 바탕으로 작성되었습니다.
