현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.
틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.
📌 개념
삽입 정렬은 수열의 왼쪽부터 순서대로 정렬한다. 알고리즘의 진행에 따라 왼쪽에는 숫자가 점차 정렬되고, 오른쪽에는 아직 확인 하지 않은 숫자가 남는다. 오른쪽의 미탐색 영역에서 숫자를 하나씩 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가며 정렬을 완성한다.
예시로 살펴 보겠다.
1부터 9까지 랜덤으로 정렬된 수열이 있다.
처음에는 왼쪽 끝의 숫자 2를 정렬이 끝난 것으로 보고 넘어간다.
2는 정렬이 완료된 상태며 이렇게 1라운드를 종료한다.
2라운드부터는 탐색하지 않은 숫자를 하나씩 꺼내 정리된 숫자와 비교해준다.
왼쪽의 숫자가 크면 두 숫자를 바꿔준다. 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때까지 반복한다.
2 < 7 이므로 별다른 변화없이 7은 정렬되며 2라운드를 종료한다.
다음 숫자인 5를 꺼내 정렬된 수들과 비교해 보겠다.
7 > 5 이므로 5와 7의 자리를 바꿔준다.
이제 그 다음 수인 2와 비교해준다.
2 < 5 이므로 변경하지 않고 자신보다 작은 숫자가 나타났기 때문에 라운드를 종료한다.
다음 9를 꺼내 비교해 주겠다.
7 < 9 이기 때문에 별다른 변화 없이 라운드를 마무리 한다.
다음 숫자 4를 정렬해 보겠다.
9 > 4 이므로 9와 4의 위치를 바꿔준다.
그 다음 수인 7과 비교를 해준다.
7 > 4 이므로 위치를 바꿔준다.
다음 5와 비교해준다.
마찬가지로 5 > 4 이므로 두 수의 위치를 바꿔준다.
마지막 숫자인 2와 비교를 해준다.
2 < 4 이므로 위치를 변경하지않고 라운드를 종료한다.
위 방식으로 6, 1, 8도 정렬해 준다.
마지막으로 3을 정렬해 주면
이렇게 1부터 9까지 오름차순으로 정렬이 완료 되었다.
📌 추가 내용
삽입 정렬의 장점은
정렬할 수가 적으면 복잡한 정렬보다 유리 할 수 있고 수열이 이미 정렬되어 있으면 매우 효율적이다.
하지만 단점은
비교적 많은 이동을 포함하며 정렬할 수가 많고 수열의 크기가 큰 경우는 적합하지 않다는 것이다.
⏱️ 시간복잡도
삽입 정렬은 각 라운드에서 미탐색 영역의 첫 번째 숫자를 그 왼쪽의 숫자와 비교한다. 위에서 본 것 처럼 만약 왼쪽에 있는 숫자가 더 작다면 더 이상 비교하지 않고 라운드를 종료한다. 정렬이 이미 되어 있다면 아무 교체도 일어나지 않을 수 있다.
그래서 최고의 경우에는 시간 복잡도가 O(n)이다.
하지만 꺼낸 숫자가 정렬이 완료된 영역의 모든 숫자보다 작을 때는 그 숫자가 왼쪽에 도착할때까지 비교하고 교체한다. 구체적으로 k라운드에서 k-1회 작업이 발생한다.
따라서 최악의 경우 2라운드에서 1회, 3라운드에서 2회 ... n라운드에서 n-1회 비교와 교체가 발생해,
최악의 경우 O(n²)이다.
그렇기 때문에 어떤 경우에도 O(n²)인 선택과 버블에 비해서 삽입 정렬이 성능적으로 우수하다.
참고 자료
그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠
[알고리즘] 삽입 정렬(insertion sort)이란 : Heee's Development Blog https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
삽입 정렬(Insertion Sort)이란? : 꾸준히 성장하는 개발자스토리 https://ssdragon.tistory.com/112
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 힙 정렬 (Heap Sort) (0) | 2024.09.09 |
|---|---|
| [알고리즘] 이진 탐색 (Binary Search) (0) | 2024.09.04 |
| [알고리즘] 선택 정렬 (Selection Sort) (0) | 2024.08.13 |
| [알고리즘] 선형 탐색 (Linear Search) (0) | 2024.08.13 |
| [알고리즘] 버블 정렬 (Bubble Sort) (0) | 2024.08.12 |
