1. 버블 정렬 (Bubble Sort)
서로 인접해 있는 요소 간의 대소 비교를 통해 정렬
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적임.
동작 방식은 인접한 두 요소간의 대소 비교를 진행함
시간 복잡도가 최고, 평균, 최악 모두 O(n^2) 이며 공간복잡도는 하나의 배열만 사용하므로 O(n)을 가짐
만약 배열에 n개의 요소가 있을 경우 1번째 원소 vs 2번째 원소를 비교하고 2번째 원소 vs 3번째 원소를 비교하고, ... n-1번째 원소 vs n번째 요소를 비교하면 1회전 비교가 끝난다.
1회전이 끝나면 가장 큰 원소는 맨 뒤에 위치하게 되므로 2회전 비교에서는 제외된다.
마찬가지로 두 번째로 큰 원소는 가장 큰 원소 앞에 위치하게 되므로 3회전 비교에서는 제외된다.
즉, 버블 정렬을 1회 수행할 때 마다 정렬해야 할 원소가 하나씩 줄어든다.
void bubbleSort(int arr[], int n) {
int temp;
for (int i = 0; i < n; i++) { //회수
for (int j = 0; j < n - 1 - i;j++) {
if (arr[j] > arr[j + 1]) { // 인접한 인덱스 비교
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2. 삽입 정렬 (Insert Sort)
정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘
첫 번째 index는 비교할 원소가 없기 때문에 두 번째 index부터 시작.
알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 O(n)의 시간 복잡도를 가진다.
단, 최악의 경우 O(n^2)
삽입 정렬을 코드로 구현하면 아래와 같다. 첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하기 위함이다.
void insertSort(int arr[], int n) {
int key, i, j;
for (i = 1; i < n; i++) {//index 1 부터 모두 확인
key = arr[i];
for (j = i - 1; j >= 0 && key < arr[j]; j--) { // key의 값보다 크면 인덱스를 +1 이동
arr[j + 1] = arr[j];
}// 아니라면 그 위치가 key가 있어야할 위치
arr[j + 1] = key; //외부에서 j를 정의했기 때문에 for문 밖에서도 사용가능
}
}
3. 선택 정렬 (Selection Sort)
선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘
시간복잡도 최선, 평균, 최악 모두 O(n^2)에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다.
동작방식 3단계로 구성
- 주어진 배열에서 최소값을 찾는다.
- 최소값을 맨 앞의 값과 바꾼다.
- 바꿔준 맨 앞 값을 제외한 나머지 원소를 동일한 방법으로 바꿔준다.
void selectSort(int arr[], int n) {
int indexMin, temp; // 최솟값 인덱스
for (int i = 0; i < n - 1; i++) {
indexMin = i;
for (int j = i + 1; j < n; j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j;
}
}
temp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = temp;
}
}
4. 퀵 정렬 (Quick Sort)
퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘
퀵 정렬에는 피봇(Pivot)이라는 개념을 사용 (피봇은 한 마디로 정렬 될 기준 원소)
피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있음
최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다.
보통 배열의 첫 번째 값이나 중앙 값을 선택
O(nlogn)
가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정한다면
이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성
다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다.
만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마침
void quickSort(int arr[], int L, int R) {
int left = L, right = R;
int pivot = arr[(L + R) / 2]; // pivot 설정 (가운데)
int temp;
do
{
while (arr[left] < pivot) // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지
left++;
while (arr[right] > pivot) // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지
right--;
if (left<= right) // left가 right보다 왼쪽에 있다면 교환
{
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
/*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
left++;
right--;
}
} while (left<= right); // left가 right 보다 오른쪽에 있을 때까지 반복
/* recursion */
if (L < right)
quickSort(arr, L, right); // 왼쪽 배열 재귀적으로 반복
if (left < R)
quickSort(arr, left, R); // 오른쪽 배열 재귀적으로 반복
}