반응형
[삽입정렬 (Insertion Sort)]
왼쪽의 그림과 같이 삽입정렬 (Insertion Sort)은 이미 정렬 완료된 배열(그림 상의 회색)과 새로운 데이터(그림 상의 빨간색)를 비교 후 새로운 데이터를 순서에 맞게 삽입해가며 정렬하는 알고리즘이다.
그림의 각 절차에 따른 설명은 하기를 참고한다.
(a) 2번째 원소인 "7"과 기정렬 완료된 배열과 비교 : 변동 없음.
(b) 3번째 원소인 "2"와 기정렬 완료된 배열과 비교 : "2"가 1번째 원소로 이동하고 이후의 원소들은 Shift right
(c) 4번째 원소인 "5"와 기정렬 완료된 배열과 비교 : "5"가 3번째 원소로 이동하고 이후의 원소들은 Shift right
(d) 5번째 원소인 "1"과 기정렬 완료된 배열과 비교 : "1"이 1번째 원소로 이동하고 이후의 원소들은 Shift right
(e) 6번째 원소인 "4"와 기정렬 완료된 배열과 비교 : "4"가 4번째 원소로 이동하고 이후의 원소들은 Shift right
(f) 완성.
장점 : 구현이 간단하다.
단점 : 배열이 길어질수록 효율이 떨어진다. 알고리즘의 효율성은 O(N2)
반응형
'프로그래밍' 카테고리의 다른 글
| Maximum subarray problem (0) | 2020.10.09 |
|---|---|
| strcmp(), strtok() (0) | 2020.10.08 |
| Merge sort (병합 정렬, 합병 정렬) (0) | 2020.08.01 |
| 구글은 소프트웨어를 어떻게 테스트하는가? (0) | 2020.05.26 |
| [C++] 디폴트 매개변수, default parameter (0) | 2019.08.14 |
