■ 정렬(Sorting)이란?
2개 이상의 데이터를 특정한 기준에 따라 순서대로 나열하는 것 (오름차순/내림차순)
■ 선택정렬 (Selection Sort)
- 주어진 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
- 시간복잡도는 O(N²)
- 선택정렬은 불안정 정렬(unstable sort)이다.
| (1) 주어진 데이터에서 가장 작은 값을 찾는다. (2) 가장 작은 값을 맨 앞에 위치한 값과 바꾼다. (3) 맨 앞의 값을 제외하고 (1), (2) 과정을 반복한다. |
| 1회차 |  |
| 2회차 |  |
| 3회차 |  |
| 4회차 |  |
| 결과 |  |
■ 삽입정렬 (Insertion Sort)
- 처리되지 않은 데이터를 하나씩 골라 앞의 값들을 보면서 적절한 위치를 찾아 삽입하는 정렬 방법
- 시간복잡도는 O(N²)
- 삽입정렬은 안정 정렬(stable sort)이다.
| (1) 2번째 Index부터 시작 (2) 선택한 Index의 값을 기준으로 기준 보다 Index 1 작은 Index의 값과 비교 (3) 비교한 값이 기준 값보다 작으면 다음 Index로 넘어감 (4) 비교한 값이 기준 값보다 크면 비교한 값의 Index 위치에 기준 값을 삽입, 비교 값 Indax는 1씩 증가 |
| 1회차 |  |
| 2회차 |  |
| 3회차 |  |
| 4회차 |  |
| 결과 |  |
■ 버블정렬 (Bubble Sort)
- 서로 인접한 두 값을 비교하여 자리를 교환(swap)하는 방법
- 시간복잡도는 O(N²)
- 버블정렬은 안정 정렬(stable sort)이다.
| (1) 인접한 두 개의 값을 비교 (2) 비교한 값 중에서 큰 값이 오른쪽에 위치 (오름차순기준) (3) 순차적으로 반복해서 비교 수행 |
| 1회차 |  |
| 2회차 |  |
| 3회차 |  |
| . . . |
|
| 결과 |  |