[알고리즘 공부] 정렬 - 선택/버블/삽입/퀵 정렬 (C언어)

선택 정렬

가장 작은 것을 선택해 앞으로 보낸다.

시간복잡도: n(n+1)/2 => O(N^2)

=> 다른 알고리즘과 비교했을 때 비효율적인 편

#include <stdio.h>

int main() {
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for (i = 0; i < 10; ++i) {
        min = 999;
        for (j = i; j < 10; ++j) {
            if (min > array[j]) {
                min = array[j];
                idx = j;
            }
        }
        tmp = array[idx];
        array[idx] = array[i];
        array[i] = tmp;
    }

    for (i = 0; i < 10; ++i) {
        printf("%d ", array[i]);
    }
    return 0;
}

 

버블 정렬

옆에 있는 값과 비교해서 작은 값을 앞으로 보낸다.

시간복잡도: n(n+1)/2 => O(N^2)

=> 구현하기 제일 쉬우나 가장 비효율적. 자리를 계속 바꿔주느라 내부 연산이 많기 때문

#include <stdio.h>

int main() {
    int i, j, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9 - i; ++j) {
            if (array[j + 1] < array[j]) {
                tmp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tmp;
            }
        }
    }

    for (i = 0; i < 10; ++i) {
        printf("%d ", array[i]);
    }
    return 0;
}

 

삽입 정렬

각 숫자를 적절한 위치에 삽입한다.

시간복잡도: n(n+1)/2 => O(N^2)

=> 필요할 때만 위치를 바꾸기 때문에 실제로는 버블/선택 정렬보다 빠름.
      거의 정렬된 상태일 때 가장 유리. 퀵, 힙, 병합 정렬보다 빠를 수도 있음.

 

#include <stdio.h>

int main() {
    int i, j, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

    for(i = 0; i < 9; ++i) {
        for(j = i; j >= 0; --j) {
            if(array[j+1] < array[j]) {
                tmp = array[j+1];
                array[j+1] = array[j];
                array[j] = tmp;
            } else break;
        }
    }

    for (i = 0; i < 10; ++i) {
        printf("%d ", array[i]);
    }
    return 0;
}

 

• 시간복잡도 O(N^2)가 넘는 알고리즘들은 데이터가 10만개만 넘어가도 일반적인 상황에서 사용하기 어렵다.
  => 빠른 정렬 알고리즘 이용해야 함

 

퀵 정렬

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다.

평균 시간 복잡도: O(N*logN)

최악 시간 복잡도: O(N^2)

=> 대표적인 분할 정복 알고리즘
   기준값(Pivot)이 있음. 보통 첫번째 원소를 피벗 값으로 설정하고 사용.

※ 이미 정렬이 되어 있는 경우에는 분할 정복의 이점을 사용하지 못하고 O(N^2)가 돼버림.

∵ 정렬할 데이터의 특성에 따라 적절한 정렬 알고리즘 사용 필요

 

#include <stdio.h>

int number = 10;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort(int *array, int start, int end) {
    // 원소가 1개일 때
    if (start >= end) return;

    int key = start; // 키는 첫번째 원소(pivot)
    int i = start + 1, j = end, tmp;

    while (i <= j) { // 엇갈릴때까지 반복
        while (array[i] <= array[key]) i++; // 키값보다 큰 값을 만날 때까지 오른쪽으로 이동
        while (array[j] >= array[key] && j > start) j--; // 키값보다 작은 값을 만날 때까지 왼쪽으로 이동
        if (i > j) { // 현재 엇갈린 상태면 키값과 작은값을 교체
            tmp = array[j];
            array[j] = array[key];
            array[key] = tmp;
        }
        else { // 엇갈리지 않았으면 두 값을 바꿔주기
            tmp = array[j];
            array[j] = array[i];
            array[i] = tmp;
        }
    }
    // 엇갈려서 빠져나오면 키값을 기준으로 왼쪽과 오른쪽에서 각각 다시 퀵정렬 수행
    quickSort(array, start, j - 1);
    quickSort(array, j + 1, end);
}

int main() {
    quickSort(array, 0, number - 1);
    for (int i = 0; i < number; ++i) printf("%d ", array[i]);

    return 0;
}

 

* 소스코드에서 딱 두 부분만 바꿔서 내림차순 정렬 가능

// 반대로 왼쪽에서부터 키값보다 큰 값을 찾고 오른쪽에서부터 키값보다 작은 값을 찾아 수행하기
while (array[i] >= array[key]) i++;
while (array[j] <= array[key] && j > start) j--;

 

- 참고할 링크

 

5. 퀵 정렬(Quick Sort)

 

 

실제 대회에서는 C++ algorithm 라이브러리 함수인 sort를 사용하는 게 가장 현명할 수 있다.

sort 함수는 퀵정렬의 원리를 이용했지만 문제점을 효과적으로 해결해 최악의 경우에도 O(N*logN)의 속도를 내기 때문

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, nums[1000000];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &nums[i]);
    sort(nums, &nums[n]);
    for (int i = 0; i < n; ++i) printf("%d\n", nums[i]);

    return 0;
}

 

병합 정렬

일단 반으로 나누고 나중에 합쳐서 정렬(합치는 순간에 정렬)

시간복잡도: O(N*logN)

=> 대표적인 분할 알고리즘
Pivot은 따로 없음.

기존의 데이터를 정렬해서 담을 추가적인 배열 공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있음

일반적인 경우 퀵 정렬보다 느리지만 어떠한 상황에서도 정확히 O(N*logN) 보장한다는 점에서 빠르고 효율적인 알고리즘

 

---

 

하지만 이미 정렬은 컴공의 오래된 연구분야이므로 이미 아주 훌륭한 정렬 관련 라이브러리가 존재함.

굳이 우리가 만들 필요 없이 C++ STL 의 sort()를 가져다 쓰면 됨!