정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.
프로그래밍을 배우기 시작하고 또 배열과 반복문을 배우고 나서 우리가 할 수 있는 것이 바로 정렬 알고리즘의 기초인 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort) 그리고 버블 정렬(Bubble Sort)이다.
선택 정렬(Selection Sort)
선택 정렬(Selection Sort)
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| int main() | |
| { | |
| int i, j, min, temp; | |
| int arr[10] = {2, 1, 3, 7, 4, 9, 6, 10, 8, 5}; | |
| for (i = 0; i < size(arr); i++) | |
| { | |
| min = i; | |
| for (j = i + 1; j < size(arr); j++) | |
| { | |
| if (arr[j] < arr[min]) | |
| { | |
| min = j; | |
| } | |
| } | |
| if (min == i) | |
| { | |
| continue; | |
| } | |
| /* | |
| arr[min] = arr[min] + arr[i]; | |
| arr[i] = arr[min] - arr[i]; | |
| arr[min] = arr[min] - arr[i]; | |
| */ | |
| swap(arr[i], arr[min]); | |
| } | |
| for (int k = 0; k < size(arr); k++) | |
| { | |
| cout << arr[k] << " "; | |
| } | |
| return 0; | |
| } |
삽입 정렬(Insertion Sort)
삽입 정렬(Insertion sort)
- 순차적으로 원소를 선택한다.
- 선택된 원소의 이전 원소들을 순차적으로 비교한다.
- 만약 선택된 원소가 이전 원소보다 작으면 교체한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| int main() | |
| { | |
| int i, j; | |
| // int temp; | |
| int arr[10] = {2, 1, 3, 7, 4, 9, 6, 10, 8, 5}; | |
| for (i = 0; i < size(arr) - 1; i++) | |
| { | |
| j = i; | |
| while (j >= 0 && arr[j] > arr[j + 1]) | |
| { | |
| /* | |
| temp = arr[j]; | |
| arr[j] = arr[j + 1]; | |
| arr[j + 1] = temp; | |
| */ | |
| swap(arr[j], arr[j+i]); | |
| j--; | |
| } | |
| } | |
| for (i = 0; i < size(arr); i++) | |
| { | |
| cout << arr[i] << " "; | |
| } | |
| return 0; | |
| } |
버블 정렬(Bubble Sort)
버블 정렬(Bubble sort)
- n번째 원소와 n+1번째 원소를 비교한다.(단, n+1은 배열의 최대 크기 - 1)
- n+1번째 원소가 작으면 서로 교체한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| int main() | |
| { | |
| int i, j; | |
| // int temp; | |
| int arr[10] = {2, 1, 3, 7, 4, 9, 6, 10, 8, 5}; | |
| for (i = 0; i < size(arr); i++) | |
| { | |
| for (j = 0; j < size(arr) - 1; j++) | |
| { | |
| if (arr[j] > arr[j + 1]) | |
| { | |
| /* | |
| temp = arr[j]; | |
| arr[j] = arr[j + 1]; | |
| arr[j + 1] = temp; | |
| */ | |
| swap(arr[j], arr[j + 1]); | |
| } | |
| } | |
| } | |
| for (i = 0; i < size(arr); i++) | |
| { | |
| cout << arr[i] << " "; | |
| } | |
| return 0; | |
| } |
정리하면서
보통 어떤 알고리즘이 좋은지를 판단할때는 시간복잡도로 판단한다. 위의 3개의 정렬 알고리즘 중 선택 정렬과 버블 정렬은 보통 n^2의 시간복잡도를 가진다. 삽입 정렬의 경우 보통은 n^2의 시간복잡도를 가지지만 정렬되어진 배열을 삽입 정렬시 n의 시간 복잡도를 가진다.
| 정렬 알고리즘 | 최적 | 평균 | 최악 |
|---|---|---|---|
| Selection Sort | n^2 | n^2 | n^2 |
| Bubble Sort | n^2 | n^2 | n^2 |
| Insertion Sort | n | n^2 | n^2 |
이외에도 많은 정렬 알고리즘이 있다. 퀵 정렬, 힙 정렬, 병합 정렬 등 많은 정렬 알고리즘들이 존재하며 이것들에 대해서는 추후 포스팅할 예정이다.