이 내용은 cs50을 공부하며 배웠던 개념인데, 구조체를 응용하는 성적 처리 프로그램에서
등록된 학생의 등수를 구해야한다는 조건에 머리가 하얘져 다시 복습하며 작성하게 되었다.
빅 오 표기법
빅 오 표기법은 알고리즘이나 함수의 시간 복잡도(시간 복잡도의 상한)를 나타내는 표기법 중 하나이다.
알고리즘의 성능을 나타내는 방법 중에서 가장 많이 사용되는 것 중 하나이며, 주어진 입력에 대한 알고리즘의 실행 시간의 상한, 즉 최악의 경우에 걸리는 시간을 나타낸다. 이때 상수항이나 낮은 차수의 항을 무시한다는 점도 알아야한다.
빅 오는 주로 다음과 같은 표기법으로 표현된다.
O(1): 상수 시간. 입력의 크기와 관계없이 일정한 실행 시간.
O(log n): 로그 시간. 입력의 로그에 비례하는 실행 시간.
O(n): 선형 시간. 입력의 크기에 비례하는 실행 시간.
O(n log n): 선형 로그 시간. 일반적인 정렬 알고리즘과 같은 알고리즘의 실행 시간.
O(n^2), O(n^3), ...: 다항 시간. 입력의 제곱, 세제곱에 비례하는 실행 시간.
O(2^n): 지수 시간. 입력의 지수에 비례하는 실행 시간.
버블 정렬
출처 : https://sylagape1231.tistory.com/17버블 정렬(Bubble Sort)은 간단한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 순서대로 정렬하는 방식이다. 쉽게 말해 위의 자료처럼 옆에 있는 자료보다 크면 위치를 바꾸고 작으면 냅두고 이 과정을 반복하여 자료를 정렬할 수 있다. 이 알고리즘은 이름 그대로 큰 값이 "올라가는(bubble up)" 것과 같은 원리로 동작한다.
C로 이를 구현해보면
//n 크기의 arr 배열에서 사용
void bubbleSort(int arr[], int n) {
int temp;
for (int i = 0; i < n-1; i++) {
// 각 반복에서 마지막 i 개의 원소는 이미 정렬되어 있으므로 제외
for (int j = 0; j < n-i-1; j++) {
// 현재 원소가 다음 원소보다 크다면 위치를 교환
if (arr[j] > arr[j+1]) {
// swap
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}이처럼 간단하게 표현할 수 있다.
이렇게 간단하지만 효율성이 매우 떨어지는 알고리즘이다. 효율이 왜 떨어지는지에 대해 앞서 배운 빅 오 표기법으로 알아보자.
효율성이 떨어지는 버블 정렬
버블 정렬이 O(N^2)의 시간 복잡도를 가지는 이유를 이해하기 위해 버블 정렬 알고리즘의 동작 원리를 살펴볼 필요가 있다.
버블 정렬은 인접한 두 원소를 비교하고, 만약 순서가 잘못되어 있다면 서로 교환하는 작업을 반복한다. 이때 전체 리스트를 훑어나가면서 가장 큰 원소가 마지막으로 이동하게 되므로, 총 N개의 원소가 있는 리스트에 대해 N-1번의 반복이 필요하다.
그리고 반복을 할 수록 전체 개수가 하나씩 줄기 때문에 전체 알고리즘의 비교 횟수는 대략적으로 (N-1) + (N-2) + ... + 1이 된다.
이는 등차수열의 합으로 나타내면 N(N-1)/2로 표현할 수 있다.
따라서 전체 비교 횟수는 약 N^2/2에 해당하며, 앞서 설명하였듯이 빅 오 표기법에서는 상수항을 무시하므로 O(N^2)의 시간 복잡도를 가진다고 말할 수 있다.
이렇듯 비효율적이어서 대부분의 실무에서는 다른 정렬 알고리즘을 사용한다고 한다.
