[Apple.py] 3주차 - 정렬(버블정렬, 선택정렬, 삽입정렬)

박민주·2024년 6월 18일
0

정렬

整列 / Sorting

뭔가가 주어졌을 때 이것을 정해진 순서대로 가지런하게 나열하는 것을 의미한다.

정렬 알고리즘

컴퓨터 분야에서 중요시되는 문제 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 문제의 핵심이다.

정렬 알고리즘의 상세

데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 사람은 수십에서 수백 개의 데이터를 다루는 데 그치지만 컴퓨터가 다뤄야 할 데이터는 보통이 백만 개 단위이며 데이터베이스 같은 경우 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다.

대부분의 경우 삽입/삭제보다는 데이터를 조회하는 것이 압도적으로 많고 조회에 필요한 것이 바로 검색이다.

안정 정렬과 불안정 정렬

안정 정렬(stable sort)은 중복된 값을 입력 순서와 동일하게 정렬한다. 예를 들어 다음 그림과 같이 지역별 발송 시각을 시간 순으로 정렬한 택배 발송 로그가 있다고 가정해보자. 안정 정렬의 경우에는 기존의 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이뤄진다. 그러나 불안정 정렬의 경우에는 시간순으로 정렬한 값을 지역명으로 재정렬하면 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞이고 만다.

이처럼 입력값이 유지되는 안정 정렬 알고리즘이 유지되지 않는 불안정 정렬 알고리즘보다 훨씬 더 유용하리라는 점은 쉽게 예상할 수 있을 것이다. 대표적으로 병합 정렬과 버블 정렬은 안정 정렬이며, 반면 퀵 정렬은 불안정 정렬이다. 게다가 입력값에 따라 버블 정렬 만큼이나 느려질 수 있다. 그야말로 최고의 알고리즘으로 칭송받는 퀵 정렬이 경우에 따라서는 최악의 알고리즘이 될 수도 있다. 이처럼 고르지 않은 성능 탓에 실무에서는 병합 정렬이 여전히 활발히 쓰이고 있다.

파이썬에서의 정렬

sort(), sorted()

python에서 자료를 정렬할 때 쓰는 방법에는 두 가지가 있는데, 바로 리스트에 sort() 메소드를 적용하는 방법과 sorted() 내장함수를 이용하는 방법입니다. 그렇다면 이 두 방법은 어떻게 다르고, 어떤 상황에서 어느 함수를 이용해야 하는지 알아보겠습니다.

list.sort()
sorted(list)

우선, sort 함수는 리스트명.sort() 형식으로 이용하는 리스트형의 메소드입니다. 즉, 이 함수는 입력값으로 리스트밖에 받지 못합니다. 또, 이 함수는 리스트 원본값을 직접 수정합니다.
또, sorted()함수와는 다르게, 정렬을 수행한 리스트를 따로 반환하지 않습니다.

sorted 함수는 sorted(리스트명) 형식으로 이용하는 내장함수이며, 리스트 원본 값은 그래도 유지합니다. sort 함수와는 다르게 어떤 입력값이든 받을 수 있습니다. 또, 이 함수는 정렬 작업을 수행한 후의 값을 반환합니다.

그럼 둘 중 뭘 쓰면 되나요?

원본을 유지해야 할 때에는 sorted() 함수를 이용하면 됩니다.
리스트 말고 다른 자료형을 정렬할 때에는 sorted() 함수를 이용하면 됩니다.
원본이 필요 없을 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.
list를 이용할 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.

Tim sort

흔히 Bubble sort, Insertion sort는 평균 시간 복잡도 𝑂(𝑛2)ㅍ으로 느린 정렬 알고리즘, Merge sort, Heap sort, Quick sort는 평균 O(nlogn)으로 빠른 알고리즘으로 알려져 있다. 정렬의 성능을 파악하는 지표에 시간은 필수이므로 Merge sort, Heap sort, Quick sort를 사용하는 것이 좋을 것 같다. 이 세 개의 정렬 알고리즘 중 어떤 것을 표준 정렬 알고리즘으로 선정하는 것이 좋을까?

최선의 경우 O(n), 최악의 경우 O(nlogn)에 추가 메모리도 들지 않는 Heap sort가 제일 성능이 좋은 알고리즘이 아닐까 하는 생각이 들 수도 있지만 평균 시간 복잡도가 O(nlogn)이라는 의미를 좀 더 자세히 살펴볼 필요가 있다.

시간 복잡도가 O(nlogn)이라는 말은 실제 동작 시간은 C×nlogn+α라는 의미이다. 상대적으로 무시할 수 있는 부분인 α 부분을 제하면 nlogn에는 앞에 C라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생긴다. 이 C라는 값에 큰 영향을 끼치는 요소로 '알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'가 있다.

참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다. 메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.

Tim sort의 등장

실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는

O(nlogn)이다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

알고리즘 종류

버블 정렬(Bubble Sort)

버블 정렬(bubble sort) 알고리즘의 개념 요약

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다.

버블 정렬(bubble sort) 알고리즘의 구체적인 개념

  • 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
  • 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블 정렬(bubble sort) 알고리즘의 예제

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

구현

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

버블 정렬(bubble sort) 알고리즘의 특징

  • 장점
    • 구현이 매우 간단하다.
  • 단점
    • 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
    • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
    • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

최적화

이전 패스에서 앞뒤 자리 비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있습니다. 따라서 이럴 경우, 이후 패스를 수행하지 않아도 됩니다.

Initial: [1, 2, 3, 5, 4]

 Pass 1: [1, 2, 3, 4, 5] => Swap 있었음
                      *
 Pass 2: [1, 2, 3, 4, 5] => Swap 없었음
                   *  *
=> 이전 패스에서 swap이 한 번도 없었으니 종료
  • 코드
def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

추가 최적화

이전 패스에서 앞뒤 자리 비교(swap)가 있었는지 여부를 체크하는 대신 마지막으로 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 됩니다. 따라서 한 칸씩 정렬 범위를 줄여나가는 대신 한번에 여러 칸씩 정렬 범위를 줄여나갈 수 있습니다.

Initial: [3, 2, 1, 4, 5]

 Pass 1: [2, 1, 3, 4, 5] => 마지막 Swap 위치가 index 1
             ^        *
 Pass 2: [1, 2, 3, 4, 5] => 중간 패스 skip하고 바로 index 1로 보낼 값 찾기
          ^     *  *  *
  • 코드
def bubble_sort(arr):
    end = len(arr) - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        end = last_swap

선택 정렬(Selection Sort)

개념

  • 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
  • 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

예제

배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

복잡도 분석

  • 선택 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
  • 시간 복잡도는 우선 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 하나의 루프에서는 현재 인덱스의 값과 다른 인덱스의 값들과 비교하여 최소값을 찾은 후 현재 인덱스에 있는 값과 상호 자리 교대를(swap)해야 해야하기 때문에 O(N)을 시간이 필요하게 됩니다. 따라서 선택 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.

알고리즘 특징

  • 선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 됩니다. 따라서, 뒤에 있는 index로 갈수록 비교 범위가 하나씩 점점 줄어드는 특성을 가지고 있습니다. (0부터 n-1까지 비교해야 되지만, n-1에서는 남은 숫자가 하나 밖어서 비교가 필요 없음)
  • 입력 배열이 정렬의 유무에 상관없이 동일한 연산량을 가지고 있기 때문에 최적화 여지가 적어서 다른 O(N^2) 알고리즘과 대비해도 성능이 떨어지는 편입니다.
  • 성능 상의 한계 때문에 실전에서는 거의 보기 힘들지만, 가장 구현이 쉬운 정렬 알고리즘이며, 한 번씩 꼭 접하게 되는 유명한 정렬 알고리즘입니다.

구현

내부 반복문에서는 현재 index부터 마지막 index까지 최소값의 index를 찾아내고, 외부 반복문에서는 이 최소값의 index와 현재 index에 있는 값을 상호 교대(swap)합니다. 각 index에 대해서 최소값을 찾기 위해 대소 비교는 여러 번 일어나나 상호 교대(swap)은 딱 한번만 일어납니다.

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

삽입 정렬(Insertion Sort)

개념

삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다.

예제

배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

특징

  • 선택/거품 정렬은 정렬의 범위가 좁아지지만 삽입 정렬은 정렬의 범위가 넓어진다.
  • 외부 반복문은 순방향, 내부 반복문은 역방향으로 진행됩니다.

복잡도 분석

  • 삽입 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
  • 시간 복잡도는 우선 루프문을 통해 정렬 범위를 2개로 시작해서 전체로 확장해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 각 패스에서는 정렬 범위에 새롭게 추가된 값과 기존 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하게 됩니다. 따라서 삽입 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
  • 아래에서 다룰 최적화를 통해서 부분적으로 정렬된 배열에 대해서 성능을 대폭 개선할 수 있으며, 특히 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있습니다.

구현

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

최적화

기존에 있던 값들은 이전 패스에서 모두 정렬되었다는 점을 활용하면 불필요한 비교 작업을 제거할 수 있습니다. 예를 들면, 아래와 같이 기존 정렬 범위 [1, 2, 3, 5]에 4가 새롭게 추가된다면, 5는 4보다 크기 때문에 swap이 필요하지만, 3은 4보다 작기 때문에 swap이 필요없습니다. 그리고 3보다 앞에 있는 숫자들은 기존 패스에서 이미 정렬을 해놓았기 때문에 당연히 3보다는 작을 것이며, 더 이상의 4와 대소 비교는 무의미합니다. 이 사실을 이용하면, 새롭게 추가된 값보다 작은 숫자를 만나는 최초의 순간까지만 내부 반복문을 수행해도 됩니다.

  • 코드
[1, 2, 3, 5, 4, ...]: 5 > 4 => swap
 *  *  *  *  ^
[1, 2, 3, 4, 5, ...]: 3 < 4 => OK => all sorted!
 *  *  *  *  *
 def insertion_sort(arr):
    for end in range(1, len(arr)):
        i = end
        while i > 0 and arr[i - 1] > arr[i]:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1

추가 최적화

swap 작업없이 단순히 값들을 shift 시키는 것만으로도 삽입 정렬의 구현이 가능합니다. 앞의 값이 정렬 범위에 추가시킨 값보다 클 경우 앞의 값을 뒤로 밀다가 최초로 작은 값을 만나는 순간 그 뒤에 추가된 값을 꼽으면 됩니다.

def insertion_sort(arr):
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        while i > 0 and arr[i - 1] > to_insert:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert

참조

네이버D2 기술 블로그 - https://d2.naver.com/helloworld/0315536
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
https://www.daleseo.com/sort-insertion/
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
https://www.daleseo.com/sort-selection/

profile
개발자 되고싶다..

0개의 댓글