개발자공부일기
정렬 알고리즘 본문
버블 정렬(Bubble sort)
버블 정렬 또는 거품 정렬은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
# include <stdio.h>
# define MAX_SIZE 5
// 버블 정렬
void bubble_sort(int list[], int n){
int i, j, temp;
for(i=n-1; i>0; i--){
// 0 ~ (i-1)까지 반복
for(j=0; j<i; j++){
// j번째와 j+1번째의 요소가 크기 순이 아니면 교환
if(list[j]<list[j+1]){
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void main() {
int i;
int n = MAX_SIZE;
int list[n] = {7, 4, 5, 1, 3};
// 버블 정렬 수행
bubble_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}선택정렬(Selection sort)
선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5
// 선택 정렬
void selection_sort(int list[], int n){
int i, j, least, temp;
// 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
for(i=0; i<n-1; i++){
least = i;
// 최솟값을 탐색한다.
for(j=i+1; j<n; j++){
if(list[j]<list[least])
least = j;
}
// 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
if(i != least){
SWAP(list[i], list[least], temp);
}
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {9, 6, 7, 3, 5};
// 선택 정렬 수행
selection_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}
삽입정렬(Insertion Sort)
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.
선택 정렬이 버블 정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다
# include <stdio.h>
# define MAX_SIZE 5
// 삽입 정렬
void insertion_sort(int list[], int n){
int i, j, key;
// 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
for(i=1; i<n; i++){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 되고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for(j=i-1; j>=0 && list[j]>key; j--){
list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j+1] = key;
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {8, 5, 6, 2, 4};
// 삽입 정렬 수행
insertion_sort(list, n);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}
Quick Sorting 퀵 정렬
퀵 정렬(Quicksort)은 범용 정렬 알고리즘이다.
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에CPU캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다.
원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.
# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)
/* low와 high가 교차할 때까지 반복(low<high) */
do{
/* list[low]가 피벗보다 작으면 계속 low를 증가 */
do {
low++; // low는 left+1 에서 시작
} while (low<=right && list[low]<pivot);
/* list[high]가 피벗보다 크면 계속 high를 감소 */
do {
high--; //high는 right 에서 시작
} while (high>=left && list[high]>pivot);
// 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
if(low<high){
SWAP(list[low], list[high], temp);
}
} while (low<high);
// low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
SWAP(list[left], list[high], temp);
// 피벗의 위치인 high를 반환
return high;
}
// 퀵 정렬
void quick_sort(int list[], int left, int right){
/* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
if(left<right){
// partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
int q = partition(list, left, right); // q: 피벗의 위치
// 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
// 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
quick_sort(list, 0, n-1);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}
5. Merge Sorting 병합 정렬
알고리즘
병합 정렬은 정렬 대상을 2개의 배열로 쪼갠 다음, 각각 정렬시킨 다음 큰 정렬된 배열로 다시 합치는 것을 말한다. 이때 배열을 쪼개어 정렬한 뒤 합치는 작업을 재귀적으로 수행한다면, 최종적으로 배열이 정렬된다는 것이다. 크기가 N인 배열을 정렬하는데 NlogN이 소요된다.
재귀적으로 구현한다는 것은 분할정복 패러다임 (문제를 잘게 쪼개어 각 부분을 해결한뒤 다시 전체 문제를 해결)을 사용한다는 것이다. 아래에서 살펴보겠지만, 분할정복은 다시 하향식 (top-down)으로 구현하는 방법과, 상향식 (bottom-up)으로 구현방법이 나뉜다.
하향식 병합 정렬 (Top-Down Merge Sort)
- 재귀(Recursion)를 이용하여 배열을 계속 반으로 나눈 뒤, 병합(Merge)하는 방식입니다.
- 재귀 호출이 많아 스택 메모리를 추가로 사용합니다.
#include <iostream>
using namespace std;
// 두 개의 정렬된 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 왼쪽 부분 배열 크기
int n2 = right - mid; // 오른쪽 부분 배열 크기
int L[n1], R[n2]; // 임시 배열 생성
// 데이터 복사
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
// 병합 과정
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
// 남은 요소 복사
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 하향식 병합 정렬 함수 (재귀)
void mergeSortTopDown(int arr[], int left, int right) {
if (left >= right) return; // 배열 크기가 1 이하이면 종료
int mid = left + (right - left) / 2; // 중앙값 찾기
mergeSortTopDown(arr, left, mid); // 왼쪽 부분 정렬
mergeSortTopDown(arr, mid + 1, right); // 오른쪽 부분 정렬
merge(arr, left, mid, right); // 정렬된 두 부분 병합
}
// 테스트 코드
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "정렬 전: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
mergeSortTopDown(arr, 0, n - 1);
cout << "정렬 후: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
상향식 병합 정렬 (Bottom-Up Merge Sort)
- 반복문(Iteration)을 사용하여 작은 부분 배열부터 병합해 나가는 방식입니다.
- 재귀 호출을 사용하지 않아 스택 메모리를 절약할 수 있습니다.
상향식 병합 정렬 C++ 코드
#include <iostream>
using namespace std;
// 두 개의 정렬된 부분 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 상향식 병합 정렬 함수 (반복문 사용)
void mergeSortBottomUp(int arr[], int n) {
for (int size = 1; size < n; size *= 2) { // 부분 배열 크기를 1, 2, 4, 8... 배로 증가
for (int left = 0; left < n - size; left += 2 * size) {
int mid = left + size - 1;
int right = min(left + 2 * size - 1, n - 1);
merge(arr, left, mid, right);
}
}
}
// 테스트 코드
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "정렬 전: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
mergeSortBottomUp(arr, n);
cout << "정렬 후: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
하향식 vs. 상향식 비교
| 비교 항목 | 하향식 (Top-Down) | 상향식 (Bottom-Up) |
| 방식 | 재귀(Recursion) | 반복문(Iteration) |
| 메모리 사용 | 추가적인 재귀 호출 스택 사용 | 추가 스택 사용 없음 |
| 구현 난이도 | 상대적으로 쉬움 | 상대적으로 어려움 |
| 시간 복잡도 | O(n log n) | O(n log n) |
| 공간 복잡도 | O(n) (추가 배열 필요) | O(n) (추가 배열 필요) |
| 특징 | DFS(깊이 우선 탐색) 방식 | BFS(너비 우선 탐색) 방식 |
재귀 호출이 이해하기 쉽다면 하향식(Top-Down)을 사용하는 것이 좋습니다.
스택 메모리 사용을 줄이고 싶다면 상향식(Bottom-Up)을 고려하는 것이 좋습니다.
📌 실무에서는 일반적으로 하향식이 더 많이 사용됩니다.
힙정렬(Heap Sort)
완전 이진트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식으로 불안정 정렬에 속한다.
최대 힙의 루트가 원소의 최댓값이라는 점을 활용하여 정렬을 수행하는 방법이다.
루트를 제외한 힙이 재정렬되는 과정이 반복되면서 정렬이 이루어진다.
성능이 좋고 가장 큰 값이나 가장 작은 값을 구할 때 유용하다.
하지만 데이터의 상태에 따라 같은 O(nlogn) 시간 복잡도 라도 조금 느리고 불안정 정렬이다.
시간복잡도는 최선, 평균, 최악 모두 O(n log n) 공간 복잡도는 O(n) 이다.
int arr[1000000];
void swap(int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void makeheap(int root, int n){
int temp = arr[root]; // 해당 부모 노드
int child = root * 2; // 왼쪽 자식 노드
while(child <= n){
// 더 큰 자식 노드 찾기
if(child<n && arr[child] < arr[child+1])
child++;
if(temp < arr[child]){ // 자식 노드가 더 클 경우
arr[child/2] = arr[child];
child *=2; // 레벨 낮추기
}
else break;
}
arr[child/2] = temp;
}
void heapsort(int n){
// 최대 힙 구성
for(int i = n / 2; i > 0; i--){
makeheap(i, n);
}
int temp;
for(int i = n; i > 0; i--){
swap(1, i);
makeheap(1, i - 1);
}
}
