정렬 알고리즘 정리(1) - 버블 정렬, 선택 정렬, 삽입 정렬

Computer Science/Algorithm

정렬 알고리즘 정리(1) - 버블 정렬, 선택 정렬, 삽입 정렬

honeybee9999 2023. 2. 13. 14:09

📌 정렬 알고리즘

- 정렬 알고리즘 (Sorting Algorithm): 원소들을 번호 순이나 사전 순과 같이 일정한 순서대로 열거하는 알고리즘.

- 우리는 일상 속에서 정렬되어 있는 수많은 것들을 접하고 있다.

나의 일상을 예시로 들자면, 개인적으로 아침마다 확인하는 MTS 속에서도 특정한 기준으로 주식 종목들이 정렬되어 있는 것을 확인할 수 있다.

그리고 오후에 코딩테스트 공부를 하기 위해 programmers와 leetcode 사이트를 접속하는데, 사이트에 있는 코딩 문제들도 특정한 기준으로 문제들이 정렬되어 있는 것을 확인할 수 있으며,

저녁 11시에 업데이트 되는 네이버 웹툰에서도 조회순, 남성 인기순 등으로 만화들이 정렬되어 있는 것을 확인할 수 있다.

이렇듯 정렬은 우리의 일상 속에서 흔히 접할 수 있다. 이러한 일상 속에서 왜 정렬이 존재하는지에 대해 생각해보자면, 답은 아주 간단하게 나온다. 바로 수많은 데이터들 중 나를 위한, 그리고 사용자들을 위한 정보를 보기 좋게 제공해주고, 우리는 가지런히 정렬되어 있는 정보들을 쉽게 찾아볼 수 있도록 하기 위함이다.

- 정렬의 핵심은 효율성이다.

사실 정렬은 어떤 방식으로든 일정한 순서대로 열겨할 수 있다. 예를 들어 자신의 서재에 메이플스토리 책이 1권부터 50권까지 뒤죽박죽 진열되어 있으며, 책을 꺼내보기 쉽도록 오름차순으로 정리하려는 상황이라고 가정해보자. 이럴 때 책을 순서대로 정렬하기 위해 꽂혀 있는 책들의 순서를 일일이 확인해가며 하나씩 정리하는 등의 여러 가지 방법으로 책들을 정렬할 수 있다.

책 50권을 앞에서 말한 방식으로 정렬하는 데에도 많은 시간이 걸리겠지만, 예를 들어 책이 50권이 아닌 500권, 혹은 5000권까지 존재한다고 가정한다면 앞에서 말한 방법으로는 상당히 많은 시간이 소요될 것이다.

그렇기 때문에 정렬은 수많은 방식으로 구현할 수 있지만 그 많은 방법들 중 어떻게 구현하는가, 즉 어떻게 구현해야 빠르게 정렬할 수 있는가가 핵심이라고 볼 수 있다.

📌 버블 정렬

- 버블 정렬 (Bubble Sort): 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘. 단순 교환 정렬이라고도 한다.

<그림 1>을 통해 버블 정렬의 동작 과정을 확인할 수 있다. 숫자가 4, 3, 1, 2, 5로 나열되어 있을 때 우선 4, 3을 비교하여 교환하고, 4, 1을 비교하여 교환하고 4, 2를 비교하여 교환하고, 4, 5를 비교한다.(4, 5는 변화가 없기 때문에 비교만 하고 교환하지는 않는다.) 한번 지나간 과정을 패스(pass)라 하며, 여기까지의 과정이 첫 번째 패스이다.

이렇게 기존의 4 -> 3 -> 1 -> 2-> 5가 3 -> 1 -> 2 -> 4 -> 5로 바뀌었으면, 그 다음 다시 1과 3을 비교하여 교환하고 2와 3을 비교하여 교환하고를 반복하여 두 번째 패스를 지나게 되며, 최종적으로 1 -> 2 -> 3 -> 4 -> 5의 순서로 정렬된다.

- 버블 정렬의 장·단점

버블 정렬의 장점
- 구현이 매우 간단하다.
- 서로 이웃한 원소만 교환하기 때문에 안정적(Stable Sort)이다.
버블 정렬의 단점
- 시간복잡도가 O(n^2)이기 때문에(최선, 평균, 최악 모두) 비효율적이다. 즉, 원소의 개수가 많으면 많아질수록 성능이 매우 떨어진다.
- 순서에 맞지 않는 요소를 인접한 요소와 교환한다.

- 버블 정렬 파이썬 코드

# 버블 정렬 알고리즘 구현
def bubble_sort(a: List) -> None:
    """버블 정렬"""
    n = len(a)
    for i in range(n-1):    # pass 횟수
        for j in range(n-1, i, -1):
            # pass(비교·교환)
            if a[j - 1] > a[j]:     # 만약 j 앞의 요소가 현재 j보다 크다면 (비교)
                a[j - 1], a[j] = a[j], a[j - 1]     # 서로의 요소를 교환 (교환)

- 버블 정렬의 시간 복잡도

원소를 비교하는 횟수가 첫 번째 패스에서는 n-1번, 두 번째 패스에서는 n-2번... 이므로 다음과 같은 결과가 나오게 된다.

T(n) = (n-1) + (n-2) + (n-3) + ... 1 = n(n-1)/2

그러므로 시간 복잡도는 O(n^2)이다. 이는 최선(Best), 평균(Avg), 최악(Worst) 모두에 해당된다.

👀 그림 1 출처: https://reactgo.com/bubble-sort-algorithm-javascript/

How to implement Bubble sort algorithm in JavaScript

Bubble sort algorithm is one of the slowest algorithms with O(n2) time complexity. In nearly sorted data bubble sort algorithm takes time…

reactgo.com

📌 선택 정렬

- 선택 정렬(Selection Sort): 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘.

아래 그림 2를 보면, 첫 번째 원소(8)에서 시작하여 원소의 뒤에 있는 가장 작은 원소(0)을 찾아 서로를 교환한다. 그 다음 두 번째 원소(5)에서 시작하여 원소의 뒤에 있는 가장 작은 원소(1)을 찾아 서로를 교환한다. 이렇게 가장 작은 원소를 선택하여 현재의 인덱스에 있는 원소와 교환하는 작업을 선택 정렬이라 한다.

- 선택 정렬의 장·단점

장점
- 버블 정렬과 같이 구현이 쉬운편이다.
- 비교하는 횟수에 비해 교환하는 횟수가 적은 편이다.
단점
- 버블 정렬과 같이 O(n^2)의 시간 복잡도를 갖기 때문에 시간이 오래 걸린다.
- 서로 이웃하지 않는 원소를 교환하므로 안정적이지 않다.

- 선택 정렬 파이썬 코드

# 단순 선택 정렬 알고리즘 구현
def selection_sort(a: List) -> None:
    """단순 선택 정렬"""
    n = len(a)
    for i in range(n - 1):
        min = i # 정렬할 부분에서 가장 작은 원소의 인덱스
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j # j를 순회하면서 가장 작은 원소를 찾아낸다.
        a[i], a[min] = a[min], a[j] # 정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환

- 선택 정렬의 시간 복잡도

루프를 도는 동안 각 인덱스에 와야 되는 최솟값을 구하기 위해 n-1, n-2, n-3번... 1번의 비교 연산을 수행한다. 그러므로 다음과 같은 결과가 나오게 된다.

T(n) = (n-1) + (n-2) + (n-3) + ... 1 = n(n-1)/2

그러므로 시간 복잡도는 O(n^2)이다. 이는 최선(Best), 평균(Avg), 최악(Worst) 모두에 해당된다.

👀 그림 2 출처: https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Selection-Sort-Animation.gif

파일:Selection-Sort-Animation.gif - 위키백과, 우리 모두의 백과사전

ko.wikipedia.org

📌 삽입 정렬

- 삽입 정렬(Insertion Sort): 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하여 정렬하는 알고리즘.

삽입 정렬은 주목한 원소보다 더 앞쪽, 즉 두 번째 원소인 5부터 주목하여 진행한다. 5는 6보다 앞쪽에 위치해야 하기 때문에 맨 앞에 삽입하고, 기존의 6을 5의 위치로 옮긴다. 그러면 5 -> 6 -> 3 -> 1 -> 8 -> 7 -> 2 -> 4와 같은 결과가 나오게 된다.

그 다음 세 번째 원소인 3을 주목한다. 3은 5보다 앞쪽에 위치해야 하므로 맨 앞에 위치한다. 이 상태에서 5, 6을 오른쪽으로 옮기면 3 -> 5 -> 6 -> 1 -> 8 -> 7 -> 2 -> 4와 같은 결과가 나오게 된다. 이후에도 계속해서 같은 작업을 수행한다.

- 삽입 정렬의 장·단점

장점
- 구현이 쉬운 편이다.
- 최선(Best)의 경우 O(n)이라는 시간 복잡도를 갖는다.
- 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이다.
단점
- 평균(Avg)과 최악(Worst)의 시간 복잡도가 O(n^2)이다.
- 버블 정렬, 선택 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다.

- 삽입 정렬 파이썬 코드

# 단순 삽입 정렬 알고리즘 구현
def insertion_sort(a: List) -> None:
    """단순 삽입 정렬"""
    n = len(a)
    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j - 1]
            j -= 1
        a[j] = tmp

- 삽입 정렬의 시간 복잡도

1. 최선의 경우

모든 원소들이 정렬되어 있는 경우, 루프를 n-1 번 도는 동안 비교 연산은 1번씩 수행된다. 그러므로 다음과 같은 결과가 나오게 된다.

T(n) = (n-1) * 1

따라서 시간 복잡도는 O(n)이 나오게 된다.

2. 최악의 경우

모든 원소들이 역순으로 되어 있는 경우, 루프를 n-1번 도는 동안 비교 연산은 n-1, n-2, n-3...번 수행하게 된다. 그러므로 다음과 같은 결과가 나오게 된다.

T(n) = (n-1) + (n-2) + (n-3) + ... 1 = n(n-1)/2

따라서 시간 복잡도는 O(n^2)이 나오게 된다.

👀 그림 3 출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

File:Insertion-sort-example.gif - Wikimedia Commons

No higher resolution available. -->