[C 자/알] 정렬 알고리즘 (버블소트와 퀵소트)

정렬 알고리즘
자료구조로 저장된 자료들을 특정한 순서로 정렬하는 알고리즘이다
정렬하기 위해서는 모든 데이터를 비교해야 한다

최소 한 번씩은 모두 짚고 넘어가야 하다 보니
정렬 알고리즘은 아무리 좋은 효율을 내더라도 O(N) 보다 느릴 수밖에 없다

여러 가지 정렬 알고리즘이 많지만,
효율은 낮지만 구현하기 쉬운 버블소트 (stable)

효율이 좋지만 unstable한 퀵소트

효율이 좋지만 stable한 머지소트가 대표적이다

 

 

정렬 알고리즘의 Stability

정렬에서 stability(안정성)란 

정렬 알고리즘이 동일한 키 값을 가진 원소들의 상대적인 순서를 유지하는 특성을 의미한다

다시 말해,

stability가 있는 정렬 알고리즘은

동일한 값의 원소들이 정렬 전에 나열된 순서가 정렬 후에도 유지되고

stablility가 없는 정렬 알고리즘은

동일한 값의 원소들이 정렬 전에 나열된 순서가 정렬 후에는 유지되지 않는 경우가 있다

 

stable 한 정렬 알고리즘에는

버블 정렬(Bubble Sort), 병합 정렬(Merge Sort), 삽입 정렬(Insertion Sort)이 있다

 

unstable 한 정렬 알고리즘에는

선택 정렬(Selection Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort)이 있다

 

---

 

버블 소트(Bubble Sort)
가장 간단한 정렬 알고리즘이다
한 번 자료구조를 순회할 때마다 가장 큰 값이 제일 위로 올라간다
큰 버블일수록 수면 위로 더 빨리 떠오르는 모습을 닮았다고 해서 버블소트라고 부른다

버블 소트의 시간 복잡도는

하나의 자리를 만들기 위해 N번의 과정을 거치고

그러한 과정을 N개의 자리만큼 반복해야 하기 때문에 O(N^2)이다

공간 복잡도는 공간의 추가나 삭제가 과정이 없기에 O(1)이다

 

버블 소트 구현 코드

#include <stdio.h>

enum
{
    LENGTH = 8
};

void Swap(int* LHS, int* RHS);
void BubbleSort(int InData[], const int InLength);

int main(void)
{
    int i, Numbers[LENGTH] = {7, 0, 6, 1, 5, 2, 4, 3};

    BubbleSort(Numbers, LENGTH);

    for (i = 0; i < LENGTH; ++i)
    {
        printf("%d ", Numbers[i]);
    }

    return 0;
}

void Swap(int* LHS, int* RHS)
{
    int Temp = *LHS;
    *LHS = *RHS;
    *RHS = Temp;
}

void BubbleSort(int InData[], const int InLength)
{
    int i, j;
    for (i = 0; i < InLength - 1; ++i)
    {
        for (j = 0; j < InLength - 1 - i; ++j)
        {
            if (InData[j + 1] < InData[j])
            {
                Swap(&InData[j], &InData[j + 1]);
            }
        }
    }
}

 

---

 

퀵 소트(Quick Sort)
가장 많이 사용되는 정렬이다
특정 자료를 기준(Pivot)으로 
해당 자료보다 작은 자료들이 모인 자료구조와
해당 자료보다 큰 자료들이 모인 자료구조로 나눈다
이 과정을 계속해서 반복하고 과정마다 새로운 기준(Pivot)을 뽑는다

퀵소트 시간 복잡도는

파티션 하나당 재정렬이 이뤄지는데 O(N)이 사용되고

계속해서 파티션이 나눠지는 횟수는 logN이기 때문에 O(N * logN)이다

 

매 단계에서 두 자료구조로 균등하게 나뉜다면, O(logN)
두 자료구조 중 한 곳으로 몰린다면, O(N)
평균은 O(NlogN), 최악은 O(N^2)이다

퀵소트에서 최악을 피하는 방법은
제일 끝을 기준 값으로 잡는 Lomuto 방식보다는
제일 끝이 아닌 다른 위치를 기준 값으로 뽑는 Hoare 방식이 좋다

그 이유는

이미 정렬이 된 자료구조에 퀵 소트를 실행하면

끝을 피봇으로 잡으면 O(N^2)의 최악의 상황이 발생할 수 있고

피봇을 랜덤 하게 혹은 가운데 값을 가져갈 경우 그 값이 최대값, 최소값일 경우는 매우 드물기 때문이다
추가적으로, 절대 O(N^2) 시간 복잡도를 허용할 수 없는 분야라면 다른 정렬을 사용하는 것이 좋다

 

퀵 소트 구현 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

enum
{
    LENGTH = 1024,
    INVALID = -1,
};

void Swap(int* LHS, int* RHS);
int Partition(int InData[], int InLeft, int InRight);
void QuickSort(int InData[], int InLeft, int InRight);

int main(void)
{
    int Data[LENGTH + 1];
    int i = 0, n = 2;

    scanf("%d", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%d", &Data[i]);
    }

    QuickSort(Data, 0, n - 1);

    for (i = 0; i < n; ++i)
    {
        printf("%d ", Data[i]);
    }

    return 0;
}

void Swap(int* LHS, int* RHS)
{
    int temp = *LHS;
    *LHS = *RHS;
    *RHS = temp;
}

int Partition(int InData[], int InLeft, int InRight)
{
    int Pivot = InData[InLeft];
    int CurrentLeft = InLeft + 1;
    int CurrentRight = InRight;

    while (CurrentLeft < CurrentRight)
    {
        while (CurrentLeft <= CurrentRight && InData[CurrentLeft] < Pivot)
        {
            ++CurrentLeft;
        }

        while (CurrentLeft <= CurrentRight && Pivot < InData[CurrentRight])
        {
            --CurrentRight;
        }

        if (CurrentLeft < CurrentRight)
        {
            Swap(&InData[CurrentLeft], &InData[CurrentRight]);
        }
    }

    Swap(&InData[InLeft], &InData[CurrentRight]);

    return CurrentRight;
}

void QuickSort(int InData[], int InLeft, int InRight)
{
    if (InRight < InLeft)
    {
        return;
    }

    int pivotIndex = Partition(InData, InLeft, InRight);
    QuickSort(InData, InLeft, pivotIndex - 1);
    QuickSort(InData, pivotIndex + 1, InRight);
}