Dev.Paul Tech, Photo, Life Blog

[CS] 알고리즘(정렬)편


CS 부수기 - 알고리즘 (정렬) 편


0. 정렬 알고리즘

이번 편은 본격적인 정렬 알고리즘(Sorting Algorithm)에 대해 알아보려고 한다.

전 편에서 다룬 탐색 알고리즘과 정렬 알고리즘에서의 안정성은 다음 링크를 확인하면 된다.

--- 탐색 알고리즘 ---

--- 정렬 알고리즘 안정성 ---


1. Selection Sort Algorithm

첫 번째로 알아볼 정렬 알고리즘은 선택 정렬 알고리즘이다.
정의는 다음과 같다.

선택 정렬 알고리즘(Selection Sort Algorithm) : 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘


그림으로 표현하는 다음과 같은 형태를 가진다.

이해를 돕기 위한 사진

전체 리스트를 탐색하며 제일 작은 속성인 (1)을 찾는다.
제일 작은 속성인 (1)은 가장 앞부분에 들어가기 때문에 리스트의 첫 번째 위치에 넣으며 1회전이 끝난다.
다음 작은 속성은 (3)으로, 이를 선택하여 (1) 다음 위치에 넣으며 2회전이 끝난다.
이러한 작업을 통해 회전을 거듭하며 정렬이 끝난다.

이러한 선택 정렬 알고리즘의 장단점은 다음과 같다.

  • 장점
    • 자료의 이동 횟수가 미리 결정됨
  • 단점
    • 안정성이 만족되지 않음
      • 값이 같은 속성이 있으면 상대적 위치가 변경될 수 있음

코드로 선택 정렬을 나타내면 다음과 같다.

// Selection Sorting Algorithm
// 선택 정렬 알고리즘

#include <stdio.h>
#define ELEMENTS 5

int main(void) {

    int index, temp;
    // 리스트 정의
    int list[ELEMENTS] = {9, 6, 1, 3, 5};
    // 전체 리스트 반복
    // 0번부터 마지막 인덱스까지 각각 한번씩 확인
    for (int i = 0; i < ELEMENTS; i++) {
        // min_value : 전체 리스트 중 제일 작은 값
        int min_value = 100;
        // 제일 작은 값을 찾기 위해 반복
        for (int j = i; j < ELEMENTS; j++) {
            // j번째 요소가 min_value 보다 작은 값이라면
            if (list[j] < min_value) {
                // index와 min_value가 제일 작은 값을 가르키도록 선언
                min_value = list[j];
                index = j;
            }
        }
        // 기존 i번째 요소를 temp로 선언
        temp = list[i];
        // i와 index값 서로 교환
        list[i] = list[index];
        list[index] = temp;
    }
    // 정렬이 끝난 후 리스트 도출
    for (int i = 0; i < ELEMENTS; i++) {
        printf("%d, ", list[i]);
    }
}

파이썬으로 작성하면 다음과 같다.

# Selection Sorting Algorithm
# 선택 정렬 알고리즘

def selection_sort(num_list):

    index, temp = 0, 0

    for i in range(len(num_list)):
        min_value = 100

        for j in range(i, len(num_list)):
            if num_list[j] < min_value:
                min_value = num_list[j]
                index = j

        temp = num_list[i]
        num_list[i] = num_list[index]
        num_list[index] = temp

    return num_list

num_list = [9, 6, 1, 3, 5]
print(selection_sort(num_list))

이러한 특성을 가진 선택 정렬 알고리즘의 시간 복잡도는 다음과 같다.

위치를 찾는 반복문 1개와 최솟값을 찾기 위한 반복문 1개가 실행되어 반복문 2개를 실행한다.
즉 최악의 경우, (n-1)만큼의 위치를 찾아서 (n-1)번 최솟값을 찾으므로,

\[(n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 = O(n^2)\]

의 시간 복잡도가 소요된다.


2. Insertion Sort Alogorithm

다음은 삽입 정렬이다.
정의는 다음과 같다.

삽입 정렬 알고리즘(Insertion Sort Algorithm) : 2번째 원소부터 시작하여, 그 앞의 원소들과 비교해 더 크다면 오르쪽으로, 작다면 왼쪽으로 삽입해 나가면 정렬하는 알고리즘


그림으로 표현하면 다음과 같다.

이해를 돕기 위한 사진

(9)와 (6)을 놓고 비교하면, (6)은 (9)보다 더 작기에 리스트의 왼쪽에 위치해야한다.
그러므로 1회전에는 (6), (9), (1), (3), (5)로 정렬을 마친다.

2회전에서는 (1)과 정렬이 끝난 (6), (9)가 서로 비교된다.
(1)은 (9)와 비교할 때 더 작기에, (9)의 왼쪽으로 들어가며 (6), (1), (9)로 자리잡게 된다.
그리고 다시 (6)과 (1)을 비교하면, (1)이 (6)보다 더 작기에 (1), (6), (9)의 형태로 정렬되며 2회전이 종료되고, 그 결과는 (1), (6), (9), (3), (5)가 된다.

이러한 삽입 정렬 알고리즘의 장단점은 다음과 같다.

  • 장점
    • 알고리즘이 단순함
    • 대부분의 원소가 정렬된 형태일 경우, 매우 효율적
    • 안정 정렬에 속함
    • 최선의 경우 O(n)의 시간 복잡도를 보임
  • 단점
    • 최악의 경우 O(n^2)의 시간 복잡도 가짐
    • 리스트의 길이가 길어질 경우 비효율적인 알고리즘

삽입 정렬을 코드로 나타내면 다음과 같다.

// Insertion Sort Algorithm
// 삽입 정렬 알고리즘

#include <stdio.h>
#define ELEMENTS 5

void insertion_sort(int list[], int n) {
    // key = 리스트의 현재 위치에 있는 값
    int i, j, key;
    // 전체 리스트 반복
    for (i = 1; i < n; i ++) {
        key = list[i];
        // j의 조건 : 양수이며, 역으로 반복
        // 이 때, list[j]값이 key보다 커야지 순서를 바꿀 수 있음
        for (j = i - 1; j >= 0 && list[j] > key; j--) {
            // j의 오른쪽 자리인 j+1에 기존 j값이 들어감
            list[j + 1] = list[j];
        }
        // 아닐경우 j+1에는 key 값이 들어감
        list[j + 1] = key;
    }
}

int main() {
    int i;
    int list[ELEMENTS] = {9, 6, 1, 5, 3};

    insertion_sort(list, ELEMENTS);
    // 결과 출력
    for (i = 0; i < ELEMENTS; i++) {
        printf("%d ", list[i]);
    }
}

파이썬으로 나타내면 다음과 같다.

# Insertion Sort Algorithm
# 삽입 정렬 알고리즘

def insertion_sort(num_list, n):

    key = 0

    for i in range(1, len(num_list)):
        key = num_list[i]

        for j in range(i, 0, -1):
            if num_list[j - 1] > num_list[j]:
                num_list[j - 1], num_list[j] = num_list[j], num_list[j - 1]

    return num_list

num_list = [9, 6, 1, 3, 5]
print(insertion_sort(num_list, len(num_list)))

이러한 삽입 정렬의 시간 복잡도는 다음과 같다.

만약 리스트가 역으로 정렬되어있다면, 모든 리스트를 반복하며 정렬해야하기 때문에 선택정렬과 같이

\[(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n - 1) / 2 = O(n^2)\]

의 시간 복잡도를 가진다.

하지만, 리스트가 모두 정렬되어 있다면 1번만 비교하면 되기에 그 시간 복잡도는

\[O(n)\]

으로 최선의 경우 O(n)으로 정리된다.


3. Bubble Sort Alogorithm

다음은 거품 정렬이라고도 부르는 버블 정렬 알고리즘이다.
정의는 다음과 같다.

버블 정렬 알고리즘(Bubble Sort Algorithm) : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘


그림으로 표현하면 다음과 같다.

이해를 돕기 위한 사진

모든 원소들을 각각 짝지어 비교하며 순서를 결정하는 형태이다.
1회전에서는 먼저 (9)와 (6)을 비교하여, 작은 값이 왼쪽으로 큰 값이 오른쪽으로 간다.
(6), (9)의 순서로 정렬 후, 다시 (9)와 (1)을 비교한다.
이런식으로 계속 비교, 정렬하다 보면 1회전 후 리스트는 (6), (1), (3), (5), (9)의 형태를 띄게 되며 1회전이 종료된다.

마찬가지의 방법으로 2회전, 3회전을 거듭하면 최종적으로 정렬된 형태가 만들어진다.

이러한 버블 정렬 알고리즘의 장단점은 다음과 같다.

  • 장점
    • 구현이 간단
  • 단점
    • 하나의 원소가 가장 왼쪽에서 가장 오른쪽으로 이동할 경우 모든 요소와의 교환이 이루어짐
      • 위 사진에서 (9)와 같은 원소들

버블 정렬을 코드로 나타내면 다음과 같다.


// Bubble Sort Algorithm
// 버블 정렬 알고리즘

#include <stdio.h>
#define ELEMENTS 5

void bubble_sort(int* list) {
    int i, j, temp;
    // 비교할 현재 위치의 값
    for (i = 0; i < ELEMENTS; i++) {
        // index i 와 비교할 값 (i 다음 값)
        for (j = i + 1; j < ELEMENTS; j++) {
            // 만약에 i < j 라면,
            if (list[i] > list[j]) {
                // 서로 스왑
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }
    }
}

int main() {
    int list[ELEMENTS] = {9, 6, 1, 3, 5};
    int i;

    bubble_sort(list);
    // 리스트 값 프린트
    for (int i = 0; i < ELEMENTS; i++) {
        printf("%d ", list[i]);
    }
}

파이썬으로 나타내면 다음과 같다.

# Bubble Sort Algorithm
# 버블 정렬 알고리즘

def bubble_sort(num_list):

    for i in range(0, len(num_list)):
        for j in range(i + 1, len(num_list)):
            if num_list[i] > num_list[j]:
                temp = num_list[i]
                num_list[i] = num_list[j]
                num_list[j] = temp

    return num_list

num_list = [9, 6, 1, 3, 5]
print(bubble_sort(num_list))

이러한 버블 정렬의 시간 복잡도는, 기본적인 로직은 앞의 선택 정렬, 삽입 정렬과 같이 리스트 전체를 돌며 포인터 값과 그 다음 값을 서로 비교하며 리스트를 반복해야하기 때문에,

\[(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n - 1) / 2 = O(n^2)\]


으로, O(n^2)의 시간 복잡도를 가진다.


4. Quick Sort Alogorithm

다음은 퀵 정렬 알고리즘이다.
정의는 다음과 같다.

퀵 정렬 알고리즘(Quick Sort Algorithm) : Charles Antony Richard Hoare에 의해 개발된 분할 정복 알고리즘. 매우 빠른 속도를 자랑하는 알고리즘

분할 정복 알고리즘(Divide and Conquer)이란, 문제를 작은 2개의 문제로 분할하여 해결하고 원래의 문제로 결과를 모아서 해결하는 방법


그림으로 표현하면 다음과 같다.

이해를 돕기 위한 사진

List 안에서 하나의 원소를 택하고 이를 pivot으로 설정한다.

일반적으로 pivot은, 가장 왼쪽 혹은 가장 오른쪽 혹은 일반적으로 가운데 값으로 설정한다.
위 사진의 경우, (5)번 속성을 pivot으로 설정한다.

그 다음, 이 pivot을 기준으로 보다 작은 값을 왼쪽으로, 보다 큰 값을 오른쪽으로 배열한다.

이렇게 정렬이 완료되면, pivot을 제외하고 전체 리스트를 pivot중심으로 쪼갠 후 재정렬한다.

위 사진을 근간으로 덧붙이자면, pivot으로 설정된 (5)번 속성을 기준으로 작은 값, 큰 값을 나열하고 이 pivot을 최종적으로 가운데의 값과 교환하면,

(1), (3), (2), (4), (5), (9), (6), (8), (7)
로 정렬된다.
이렇게 정렬된 리스트를 다시 (5)번 속성을 기준으로 왼쪽과 오른쪽을 나누어, 각각 다시 pivot값을 설정하고 재배열 한다.

이러한 퀵 정렬의 장단점은 다음과 같다.

  • 장점
    • 시간 복잡도가 다른 정렬 알고리즘에 비해 매우 빠름
    • 추가 메모리 공간을 필요로 하지 않음
  • 단점
    • 리스트가 정렬된 상태라면 불균형 분할 즉, pivot값의 선택에 의해 오히려 더 많은 시간이 소요될 수 있음

퀵 정렬을 코드로 나타내면 다음과 같다.

// Quick Sorting Algorithm
// 퀵 정렬 알고리즘

#include <stdio.h>
#define ELEMENTS 10

void quick_sort(int list[], int left, int right) {
    // L, R = 포인터
    int L = left, R = right;
    int temp;
    // pivot => 초기 리스트의 경우 list[4] = 1에 해당
    int pivot = list[(L + R) / 2];

    while (L <= R) {
        // list[L]이 피벗보다 작다면 올바른 위치에 존재
        // 포인터 L은 +1이 됨
        // 피벗보다 크다면 반복은 멈추고 자리를 바꾸기 위해 다음으로 넘어감
        while (list[L] < pivot) {
            L++;
        }
        // list[R]이 피벗보다 크다면 올바른 위치에 존재
        // 포인터 R은 -1이 됨
        // 피벗보다 작다면 반복 멈추고 자리를 바꾸기 위해 다음으로 넘어감
        while (list[R] > pivot) {
            R--;
        }
        // 두개의 속성 위치 변경
        if (L <= R) {
            if (L != R) {
                temp = list[L];
                list[L] = list[R];
                list[R] = temp;
            }
            // 바꾼 후, 포인터는 다음 인덱스를 가르키기 위해 각각 +1, -1 됨
            L++;
            R--;
        }
    }
    // 1회전이 종료되면 포인터 L과 right, 포인터 R과 left를 비교
    // L이 right보다 작다면, 1회전이 끝난 리스트, L과 right 값이 새로운 파라미터가 되어 2회전 시작
    if (left < R) {
        quick_sort(list, left, R);
    }
    // R이 left보다 크다면, 1회전이 끝난 리스트, R과 left 값이 새로운 파라미터가 되어 2회전 시작
    if (L < right) {right);
        quick_sort(list, L, right);
    }
}

int main() {
    int list[ELEMENTS] = {5, 2, 3, 6, 1, 9, 0, 7, 8, 4};
    quick_sort(list, 0, 9);
    for (int i = 0; i < 10; i++) {
        printf("%d ", list[i]);
    }
}

파이썬으로 나타내면 다음과 같다.

def quick_sort(num_list, left, right):
    L, R = left, right
    temp = 0
    pivot = num_list[(L + R) // 2]

    while L <= R:
        while num_list[L] < pivot:
            L += 1
        while num_list[R] > pivot:
            R -= 1

        if L <= R:
            if L != R:
                temp = num_list[L]
                num_list[L] = num_list[R]
                num_list[R] = temp
            L += 1
            R -= 1

    if left < R:
        quick_sort(num_list, left, R)
    if L < right:
        quick_sort(num_list, L, right)

    return num_list

num_list = [5, 2, 3, 6, 1, 9, 0, 7, 8, 4]
print(quick_sort(num_list, 0, 9))

이러한 퀵 정렬의 시간복잡도는 다음과 같다.

퀵 정렬의 경우 앞서 말한 것처럼 분할 정복 알고리즘에 속하기에, 트리(Tree)구조를 띄고 있다.
리스트가 2개씩 나누어지며 점점 분할되었다가 다시 합쳐지는 구조를 띄기에,
그 깊이를 $ n = 2^k $로 가정하면,

\[n = 2^k, K = log_2n\]

이며, 각 단계별 비교 연산은 단계당 n번으로,

\[n * log_2n = nlog_2n\]

으로 정리된다.

즉, nlog2n의 시간 복잡도를 가지게 된다.


5. Merge Sort Alogorithm

마지막은 합병 정렬이다.
정의는 다음과 같다.

합병 정렬 알고리즘(Merge Sort Algorithm) : John Von Neumann이 개발한 알고리즘으로 안정 정렬이며 분할 정복 알고리즘의 종류 중 하나. 하나의 리스트를 두개의 균등한 크기로 분할하고, 분할된 부분리스트로 정렬 후 부분 리스트를 다시 합하며 정렬하게 하는 알고리즘


그림으로 표현하면 다음과 같다.

이해를 돕기 위한 사진

위 사진과 같이 나열된 리스트가 있다고 가정하자.

총 8개의 속성을 먼저 4개씩 분할한다.
그 후 첫 (2), (6), (3), (7)의 속성을 다시 두개로 분할한 후 다시 두개로 나누면 최종적으로 모두가 각각의 독립적인 속성이 된다.

먼저 (2)와 (6)을 다시 합친다.
이 때, 둘의 크기를 비교하여 작은 속성이 앞으로, 큰 속성이 뒤로 오도록 정렬한다.

마찬가지로 (3)과 (7)도 정렬 후, 다시 (2), (6), (4), (7)로 분할되어 있는 두개의 리스트를 합친다.
이런 식으로 리스트를 재정렬하며 합치면, 최종적으로 (2), (3), (6), (7)로 정렬된다.

이와 같이 분할 정복 즉, 트리 구조를 띄며 재정렬하게 된다.

이러한 합병 정렬의 장점과 단점은 다음과 같다.

  • 장점
    • 안정적인 정렬
      • Linked List로 구성하게 되면, 링크 인덱스만 변경하면 되기에 데이터 이동은 매우 작아짐
      • 크기가 큰 Linked List에서는 매우 효율적
  • 단점
    • 레코드가 배열(Array)일 경우, 임시 배열이 필요
      • 제자리 정렬이 아님
    • 레코드의 크기가 커질 경우 시간적 낭비가 발생

합병 정렬을 코드로 나타내면 다음과 같다.

// Merge Sort Algorithm
// 합병 정렬 알고리즘

#include <stdio.h>
#define ELEMENTS 10

// 나눠진 리스트 합치기 위한 함수
void merge(int list[], int left, int mid, int right) {
    int temp_list[ELEMENTS];
    int L = left;
    int R = mid + 1;
    int n = left;

    // 속성 L과 속성 R 비교
    // mid보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬
    while (L <= mid && R <= right) {
        // if L <= R
        if (list[L] <= list[R]) {
            // 왼쪽으로
            temp_list[n++] = list[L++];
        } else {
            // 아니면 오른쪽으로
            temp_list[n++] = list[R++];
        }
    }
    // L이 mid보다 큰 경우
    if (L > mid) {
        // 시작점은 R, 반복문은 right 방향으로
        for (int i = R; i <= right; i++) {
            temp_list[n++] = list[i];
        }
    } else {
        // L 이 mid보다 작거나 같을 경우
        // 시작점은 L, 반복문은 L부터 mid까지
        for (int i = L; i <= mid; i++) {
            temp_list[n++] = list[i];
        }
    }
    // 리스트 재정렬
    for (int i = left; i <= right; i++) {
        list[i] = temp_list[i];
    }
}

// left >= right일 때 까지 리스트 나누기
// 나누기가 끝나면 합병을 위해 merge함수로 넘어감
void merge_sort(int list[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;
    merge_sort(list, left, mid);
    merge_sort(list, mid + 1, right);
    merge(list, left, mid, right);
}

int main() {
    int list[ELEMENTS] = {5, 3, 2, 7, 8, 1, 9, 0, 6, 4};
    merge_sort(list, 0, 9);
    for (int i = 0; i < 10; i++) {
        printf("%d ", list[i]);
    }
    return 0;
}

파이썬으로 나타내면 다음과 같다.

# Merge Sort Algorithm
# 합병 정렬 알고리즘

def merge(num_list, left, right):
    temp_list = []
    mid = (left + right) // 2
    L = left
    R = mid + 1

    while L <= mid and R <= right:
        if num_list[L] <= num_list[R]:
            temp_list.append(num_list[L])
            L += 1
        else:
            temp_list.append(num_list[R])
            R += 1

    while L <= mid:
        temp_list.append(num_list[L])
        R += 1

    while R <= right:
        temp_list.append(num_list[R])
        R += 1

    for i in range(left, right + 1):
        num_list[i] = temp_list[i - left]

    return num_list


def merge_sort(num_list, left, right):
    if left >= right:
        return

    mid = (left + right) // 2
    merge_sort(num_list, left, mid)
    merge_sort(num_list, mid + 1, right)
    return merge(num_list, left, right)

num_list = [5, 3, 2, 7, 8, 1, 9, 0, 6, 4]
merge_sort(num_list, 0, 9)
print(num_list)

시간 복잡도는 퀵 정렬과 마찬가지로 트리의 구조를 띄기에,

\[nlog_2n\]

으로 결정된다.


6. 마치며

길고 긴 여정을 끝으로 정렬 알고리즘이 끝났다.

이 이외에도 여러 정렬 알고리즘이 존재하지만, 나중에 추가적으로 더 공부하여 포스팅할 예정이다.

그럼, Adios

Written on September 11th, 2023 by Dev.Paul
Feel free to share!

You may also enjoy: