Incremental approach로 본 Insert sort algorithm
두비니
·2023. 6. 28. 02:52
Incremental approach로 본 Insert Sort Algorithm
0. 개요
알고리즘을 구상할 때 여러 가지 접근 방법이 있겠지만, 크게 두 가지 approach에 대해서 다룰 예정이다.
첫 번째는 Incremental Approch이고, 대표적인 예시인 Insert Sort Algorithm에 대해서 알아볼 것이다.
1. Incremental Approach(증가적 도달)
Incremental Approach란 위에서도 이야기했듯, 문제를 푸는 하나의 시각이다. 자세히 알아보자.
GPT는 쪼개서 풀어내는 방법을 'Subproblems'라고 했는데, 추후 한 번 더 이야기하겠지만 작은 부분 문제를 순차적으로 해결하면서 전체적인 문제 해결을 추구하는 방법이다. 이는 작은 부분 문제를 독립적으로 해결한 후 결과를 통합하여 전체적인 문제를 해결하는 divide and conquer와는 조금 다른 양상을 띈다.
말로는 애매할 수 있으니 실제 알고리즘을 보자.
2. Insertion Sort (삽입정렬)
삽입정렬의 정의는 다음과 같다 (Thank you Wikipedia)
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
과정도 위와 같다. 위에서 이야기했던 Incremental Approach의 측면에서 보면 다음과 같이 다시 설명할 수 있다.
- 작은 subarray부터 정렬하는 것으로 시작해, 해당 subarray에 요소를 하나씩 더해가는 구조
- subproblem: subarray를 정렬하는 것
따라서 삽입정렬의 의사코드는 다음과 같다.
3. 알고리즘 분석
이제 삽입정렬 자체에 대해서 이해했으니, 알고리즘에 대한 성질을 알아보자.
알고리즘을 분석할 때는 알고리즘 실행 시 필요한 단계 수(시간 복잡도), 메모리 공간(공간 복잡도), 네트워크 대역폭 등의 리소스 예측의 관점이 필요하다.
3.1. Time Complexity
위 의사코드를 참고하면, 알고리즘이 실행되는 횟수는 4, 5, 6번이 얼마나 많이 실행되느냐에 달려있다.
Best Case의 경우, 모든 input이 정렬되어있는 상태로 입력되는 경우이기 때문에 O(n)이다.
Worst Case의 경우, 모든 input이 역순으로 정렬되어있는 상태로 입력되는 경우이기 때문에 O(n^2)이다.
참고로 직접 Time Complexity에서 계산을 하고 싶은 경우 다음 글을 참고하자: https://hey-stranger.tistory.com/128
[알고리즘] insertion sort - loop invariants & runtime
(2021.10.06) 알고리즘 수업들으면서 정리하기 2탄 2주차+3주차 내용 Insertion sort - loop invariants statement: j-1 번째까지는 정렬되어 있음이 계속 보장된다. Initialization(초기조건): first iteration 전에도 참이
hey-stranger.tistory.com
따라서 Incremental Approach에서는 두 가지에 따라 Time Complexity가 정해지는 것을 알 수 있다.
- 입력값의 크기 (n)
- 입력값의 상태 (얼마나 정렬되어있는지)
'Coding_Algorithm > DS_Algorithm' 카테고리의 다른 글
| Growth of Function (0) | 2023.06.30 |
|---|---|
| Divide and Conquer 관점에서 본 Merge Sort (0) | 2023.06.29 |
| 알고리즘 & Halting Problem (0) | 2023.06.27 |
| [C로 쓴 자료구조론] 1장 연습문제-12번(멱급수) 풀이 (1) | 2020.05.17 |
| [C로 쓴 자료구조론] 1장 연습문제-11번(하노이의 탑) 풀이 (0) | 2020.05.16 |
