버블정렬, 선택정렬, 삽입정렬 - 정렬알고리즘
버블정렬, 선택정렬, 삽입정렬 - 정렬알고리즘 — #정보처리기사 #버블정렬 #선택정렬 #삽입정렬 #정렬알고리즘 #개발자의도구들 24년도 1회차 정보처리기사 ...
#정보처리기사 #버블정렬 #선택정렬 #삽입정렬 #정렬알고리즘 #개발자의도구들
24년도 1회차 정보처리기사 필기 시험대비 공부를 진행하였습니다.
\* 본글은 PC버전에 최적화 되어있습니다.
**\\ **공부방법론은 가장 첫글에 있습니다. 참고하실 분들은 참고하세요! \\ - 개발자의도구들
\\ 정보처리기사 전체 총 정리는 여기 있습니다!! \\
2과목, 소프트웨어 개발
view
삽입정렬
삽입정렬은 앞에서 부터 차례대로 비교하고 작은 순서대로 삽입한다고 해서 삽입정렬입니다.
버블정렬과 비슷한 방법이라 헷갈릴 수도 있습니다.
삽입정렬 순서
| 초기상태 | 7 | 2 | 6 | 3 | 9 | 1 |
|---|---|---|---|---|---|---|
| 1회전 | 2 | 7 | 6 | 3 | 9 | 1 |
| 2회전 | 2 | 6 | 7 | 3 | 9 | 1 |
| 3회전 | 2 | 3 | 6 | 7 | 9 | 1 |
| 4회전 | 2 | 3 | 6 | 7 | 9 | 1 |
| 5회전 | 1 | 2 | 3 | 6 | 7 | 9 |
설명
두 번째 값부터 시작하여 이전 값들과 모두 비교하고 알맞는 자리에 찾아가는 방식이다. 앞으로 삽입되면 뒤의 값들이 전부 한칸씩 밀린다.
1회차: 초기상태의 2와 7을 비교한다 -> 2 <7 이니 순서를 바꾼다.
2회차: 6과 2, 7을 비교한다 -> 2 < 6 <7
3회차: 3과 2, 6, 7을 비교한다 -> 2 < 3 < 6 <7
4회차: 9과 2, 3, 6, 7을 비교한다 -> 2 < 3 < 6 < 7 < 9
5회차: 1과 2, 3, 6, 7, 9를 비교한다 -> 1 < 2 < 3 < 6 < 7 < 9
n개의 원소를 n 번비교 하니 빅오표기법으로는 O(N²)의 속도를 지닌다.
버블정렬
버블정렬은 삽입정렬과 비슷한듯 보이지만, 뚜렷한 다른 특징을 지닙니다.
삽입정렬이 자신을 제외한 앞의 값들과 전체를 비교하는 대신, 버블정렬은 자신의 옆에 있는 값만 비교합니다.
그림으로 기억하기: ⏜ ⏜ ⏜ ⏜ ⏜ ⏜ ⏜ ⏜ (거품이 보글보글 올라오는 모양)
| 초기상태 | 7 | 2 | 6 | 3 | 9 | 1 |
|---|---|---|---|---|---|---|
| 1회전 | 2 | 7 | 6 | 3 | 9 | 1 |
| 2 | 6 | 7 | 3 | 9 | 1 | |
| 2 | 6 | 3 | 7 | 9 | 1 | |
| 2 | 6 | 3 | 7 | 9 | 1 | |
| 2 | 6 | 3 | 7 | 1 | 9 | |
| 2회전 | 2 | 6 | 3 | 7 | 1 | 9 |
| 2 | 3 | 6 | 7 | 1 | 9 | |
| 2 | 3 | 6 | 7 | 1 | 9 | |
| 2 | 3 | 6 | 1 | 7 | 9 | |
| 2 | 3 | 6 | 1 | 7 | 9 | |
| 3회전 | 2 | 3 | 6 | 1 | 7 | 9 |
| 2 | 3 | 6 | 1 | 7 | 9 | |
| 2 | 3 | 1 | 6 | 7 | 9 | |
| 2 | 3 | 1 | 6 | 7 | 9 | |
| 2 | 3 | 1 | 6 | 7 | 9 | |
| 4회전 | 2 | 3 | 1 | 6 | 7 | 9 |
| 2 | 1 | 3 | 6 | 7 | 9 | |
| 2 | 1 | 3 | 6 | 7 | 9 | |
| 2 | 1 | 3 | 6 | 7 | 9 | |
| 2 | 1 | 3 | 6 | 7 | 9 | |
| 5회전 | 1 | 2 | 3 | 6 | 7 | 9 |
1회전 할때마다 모든 수를 돌아 양 옆의 수와 비교한다.
단점은 위 케이스처럼 1이 맨뒤에 있을때 회전이 많아져 시간이 더 걸려 비효율적일 수 있다는 것이다.
역시나 n개의 요소를 n번 비교하므로 O(N²)이다.
선택정렬
선택정렬도 위 두 정렬과 유사하게 보이나 큰 차이점이 있다. 바로 자리값을 고정으로 두고 모든 요소들을 바로 바로 비교하는 것이다.
자리를 "선택" 한다는 개념으로 이해하면 편하다.
| 초기상태 | 7 | 2 | 6 | 3 | 9 | 1 |
|---|---|---|---|---|---|---|
| 1회전 | 2 | 7 | 6 | 3 | 9 | 1 |
| 2 | 7 | 6 | 3 | 9 | 1 | |
| 2 | 7 | 6 | 3 | 9 | 1 | |
| 2 | 7 | 6 | 3 | 9 | 1 | |
| 1 | 7 | 6 | 3 | 9 | 2 | |
| 2회전 | 1 | 6 | 7 | 3 | 9 | 2 |
| 1 | 3 | 7 | 6 | 9 | 2 | |
| 1 | 3 | 7 | 6 | 9 | 2 | |
| 1 | 2 | 7 | 6 | 9 | 3 | |
| 3회전 | 1 | 2 | 6 | 7 | 9 | 3 |
| 1 | 2 | 6 | 7 | 9 | 3 | |
| 1 | 2 | 3 | 7 | 9 | 6 | |
| 4회전 | 1 | 2 | 3 | 7 | 9 | 6 |
| 1 | 2 | 3 | 6 | 9 | 7 | |
| 5회전 | 1 | 2 | 3 | 6 | 7 | 9 |
자리값은 고정이고, 변경되는 순간 순간을 그대로 반영 후 정렬하고 있습니다.
(자리값을 선택 하는 정렬임을 기억하세요.)
역시나 n개의 요소를 n번 비교하기 때문에 O(n²)입니다.