O(n²)인 정렬 알고리즘 (버블 정렬, 선택 정렬, 삽입 정렬)

여러가지 정렬 알고리즘들을 배우기 앞서...

실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용한다. 

예를 들면, 정렬 대상을 특정 크기만큼 만들 때에는 퀵 정렬을 쓰다가 특정크기가 되었을 때에는 작은 규모에서 강점을 보이는 삽입 정렬을 쓴다거나 한다.

혹은 특정 횟수 이상 재귀호출이 발생하면 O(NlogN)이 보장되는 힙정렬을 쓴다.

O(n²) 인 정렬 알고리즘

계싼 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어나는 알고리즘들이다. 그 종류를 살펴보도록 하자.

버블 정렬 (Bubble Sort)

버블 정렬(Bubble sort)는 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시 인접한 원소들을 교환하는 방법이다. 

첫 번째 원소와 두번째 원소를 비교하여 정렬하고, 2번째와 세번째, 그리고 n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아간다. 마지막 n번째를 제외하고 n-1번째까지 해서 최대  번 정렬한다. 

거의 대부분의 상황에서 비효율적인 알고리즘이다. 가장 손쉽게 구현할 수 있지만 알고리즘적 관점에서 보면 매우 최악인 방법이다. 입력량이 적다면 모를까 실제 개발에서는 전혀 사용하지 않는다고 한다. (....)

아래는 버블 정렬을 C언어로 구현한 코드이다. 

#include <stdio.h>
 
#define MAX 5005
 
int d[MAX];
 
void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
 
int main()
{
    int n; 
 
    scanf("%d", &n);
 
    for(int i = 0 ; i < n ; i++)
        scanf("%d", &d[i]);
 
    for(int i = 0 ; i < n - 1 ; i++)
    {
        for(int j = 0; j < n - i - 1; j++)
        {
            if(d[j] > d[j + 1])
            {
                swap(&d[j], &d[j + 1]);
            }
        }
    }
 
    for(int i = 0 ; i < n ; i++)
        printf("%d ", d[i]);
 
    return 0;
}
 

이 것은 이전에 올렸던 버블 정렬 관련 게시글이다. 개선된 버블정렬 코드도 있고 하니 한번 참고하길 바란다.

https://butter-shower.tistory.com/9?category=686507

선택 정렬 (Selection Sort)

쭉 훑어서 첫 번째 시도에 가장 작은게 첫 번째, 두번째 신호에서 가장 작은게 두 번째...

이런 방식으로 정렬하는 알고리즘이다. 

매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(n²) 이다. 

어떻게 정렬되어있든 일관성 있게  에 비례하는 시간이 걸린다는게 특징이다. 버블 정렬보다 두 배 정도 빠르다.

선택 정렬 코드는 아래와 같다.

#include <stdio.h>
#define MAX 5005
int arr[MAX];
int N;
void Swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void selection_sort(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        int minidx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[minidx] > arr[j]) {
                minidx = j;
            }
        }
        Swap(&arr[minidx], &arr[i]);
    }
}
int main() {
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d",&arr[i]);
    }
    selection_sort(arr, N);
    for (int i = 0; i < N; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
    

삽입 정렬 (Insertion Sort)

삽입 정렬을 알기 쉽게 표현한 움짤이다.

삽입 정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나누어 원소를 순차적으로 탐색하면서 해당 원소를 정렬이 된 부분에 끼워 넣는 정렬 방법을 말한다. 

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워 넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어낸다.

평균적으로 O(n2)중  빠른 편이나, 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 작은 게 뒤쪽에 몰려있으면 매우 험난할 것이다..

삽입 정렬의 코드는 아래와 같다.

첫 번째 줄에 원소의 갯수, 두 번째 줄에 원소들을 입력받아 삽입정렬을 사용하는 알고리즘이다.

#include <stdio.h>
 
#define MAX 5005
 
int d[MAX], n;
 
int main() {
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &d[i]);
 
    for (int i = 0; i < n; i++) {
        int temp = d[i];
 
        int j = i - 1;
 
        for (; j >= 0; j--) {
 
            if (d[j] < temp)
                break;
 
            d[j + 1] = d[j];
        }
 
        d[j + 1] = temp;
    }
 
    for (int i = 0; i < n; i++)
        printf("%d ", d[i]);
 
    return 0;
}