[SW 정글 7일차] 정렬 알고리즘 1

오늘은 정렬 알고리즘에 대해 정리해보려고 한다.

정글에 들어오기 전, 정렬 알고리즘을 나동빈님 책과 유튜브 강의로 본 적은 있지만 파이썬에서는 sort() 내장함수가 시간복잡도 면에서 좋기 때문에 정렬 알고리즘을 파헤치기 보다는 그냥 정렬 문제면 sort()써야지라는 생각 뿐이였다.

오늘 이렇게 나에게 시간이 주어진만큼 정렬 알고리즘을 제대로 공부를 할 수 있었다.

 

 

 

1. 버블 정렬 (bubble sort)

버블 정렬은 정렬 알고리즘 중 기본적인 알고리즘으로 이웃하고 있는 두 원소의 대소 관계를 비교하여 자리 교환이 필요할 시에 교환을 반복하는 알고리즘이다.

아래의 배열을 버블 정렬을 이용하여 오름차순으로 정리한다고 해보자.

뒤에서부터 이웃한 원소 2개씩 대소 비교를 하며 왼쪽의 값이 오른쪽의 값보다 작거나 같도록 만들어준다.

이렇게 1번 진행하면 배열 중 가장 작은 값인 1이 맨 앞으로 오게 되고 정렬을 시행할 범위가 1줄어든다.

그 다음 1번 더 진행하면 아래의 그림과 같이 두 번째로 작은 값인 2가 두 번째 자리로 오게 되면서 정렬을 시행할 범위가 1줄어든다.

이렇게 n - 1번 반복한다면 우리가 원하는 오름차순 배열이 완성될 것이다.

그러면 이제 버블 정렬을 구현한 코드를 봐보자.

def bubble_sort(n):
    arr_length = len(n)
    for i in range(arr_length - 1):
        for j in range(arr_length - 1, i, -1):
            if n[j - 1] > n[j]:
                n[j - 1], n[j] = n[j], n[j - 1]

간단하게 배열을 받으면 배열의 길이 - 1만큼 반복을 하면서 맨 뒤 2개 원소를 대소 비교를 하면서 뒤 원소가 더 크면 앞의 원소와 swap하는 형태이다.

여기서, 코드의 실행 시간을 단축하기 위해서는 n - 1번 수행하기 전에 정렬이 완료되었으면 정렬을 멈추게 하는 것이다.

이것을 위해서는 원소 교환이 없을 때를 체크하면되는데 코드를 보면 아래와 같다.

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

        if exchange_num == 0:
            break

조금 더 실행 시간을 줄일 수 있는 방법은 위 코드에서 교환을 탐색할 범위를 줄여주는 것이다.

만약, 2번째 정렬 반복 순서인데 이미 앞의 원소 3개가 정렬이 된 상태라면 굳이 맨 앞까지 가서 탐색할 필요는 없이 때문이다.

이 방법을 위해서는 교환이 이루어졌을 때의 인덱스 번호를 저장하여 다음 탐색 시에 해당 인덱스전까지만 대소 비교를 하면 될 것이다.

def bubble_sort(n):
    arr_length = len(n)
    k = 0
    while k < n - 1:
    	exchange_num = 0
        for j in range(arr_length - 1, i, -1):
            if n[j - 1] > n[j]:
                n[j - 1], n[j] = n[j], n[j - 1]
                exchange_num += 1
                k = j
   
        if exchange_num == 0:
            break

 

 

 

2. 단순 선택 정렬 (straight selection sort)

단순 선택 정렬은 배열 내에서 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 방식이다.

전체적인 매커니즘은 아래와 같다.

1) 아직 정렬하지 않은 부분에서 값이 가장 작은 원소를 선택한다.

2) 선택한 가장 작은 원소와 아직 정렬하지 않은 부분의 가장 앞에 있는 원소를 교환한다.

 

단순 선택 정렬도 버블 정렬과 마찬가지로 n - 1번 반복하면 전체 정렬이 완료된다.

코드를 보면 아래와 같다.

def selection_sort(n):
    length_arr = len(n)
    for i in range(length_arr - 1):
        min = i
        for j in range(i + 1, length_arr):
            if n[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

단순 선택 정렬은 중복된 값이 있으면 두 원소의 순서가 정렬 후에 바뀔 수 있으므로 안정적이지않은 정렬이다.

 

 

 

3. 단순 삽입 정렬 (straight insertion sort)

단순 삽입 정렬은 배열 중 하나의 원소를 선택하고 선택한 원소의 앞쪽을 비교하면서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다.

단순 선택 정렬과의 차이점은 배열 내의 값이 가장 작은 원소를 선택하는 것이 아니라는 것이다.

그림을 보며 단순 삽입 정렬이 어떻게 이루어지는지 알아보자.

단순 삽입 정렬의 시작은 배열의 두 번째 위치의 원소부터 선택되어 실행된다.

6은 앞에 있는 원소보다 크므로 그대로 있는다.

다음으로 세 번째 원소인 4를 선택하고 정렬을 실행한다.

4의 앞에 있는 6보다 작으므로 6은 4의 위치(세 번째)에 삽입되고 다음으로 1보다는 크므로 4는 두 번째 위치에 삽입되게 된다.

다음으로 네 번재 원소인 2를 선택하고 정렬을 실행한다.

2의 앞에 있는 6보다 작으므로 6은 2의 위치에 삽입(네 번째)되고 다음으로 4보다 작으므로 4는 6의 위치(세 번째)에 삽입되고 1보다는 크므로 2는 두 번재 위치에 삽입되게 된다.

이런식으로 계속해서 정렬이 반복되고 마지막 여섯 번째 원소에 대해 정렬을 하게 되면 오름차순이 완성된다.

 

단순 삽입 정렬을 코드로 구현하면 아래와 같다.

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

단순 삽입 정렬은 서로 떨어져 있는 원소를 교환하는 방식이 아니므로 안정적인 정렬 알고리즘이고 적은 원소를 가진 배열을 정렬을 할 때에는 효율적인 알고리즘이다.

위에서 알아본 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬은 시간 복잡도가 O(n^2)으로 효율적인 알고리즘은 아니다.

이 중 단순 삽입 정렬을 조금 더 효율적으로 개선한 방법으로 이진 삽입 정렬이 있다.

def binary_insertion_sort(arr):
    length_arr = len(arr)
    for i in range(1, length_arr):
        key = arr[i]
        first_searching_index = 0
        last_searching_index = length_arr - 1

        while True:
            center_searching_index = (first_searching_index + last_searching_index) // 2
            if arr[center_searching_index] == key:
                break

            elif arr[center_searching_index] < key:
                first_searching_index = center_searching_index + 1

            else:
                last_searching_index = center_searching_index - 1

            if first_searching_index > last_searching_index:
                break

    insertion_index = center_searching_index - 1 if first_searching_index <= last_searching_index else last_searching_index + 1

    for j in range(i, insertion_index, -1):
        arr[j] = arr[j - 1]
    arr[insertion_index] = key

이진 삽입 정렬에 대한 내용은 아래의 링크를 확인하면 좋을 것 같다.

https://st-lab.tistory.com/262

자바 [Java] - 이진 삽입 정렬 (Binary Insertion Sort)

 

 

 

---

오늘은 정글에 들어와서 처음 맞이하는 일요일이다.

정글은 기본적으로 코어타임이 월요일~토요일 오전 10시부터 저녁 10시까지이다.

(물론 오전 10시~ 저녁 10시를 딱 지켜서 오가는 동료들은 없고 다들 정말 열심히 공부한다..)

이범규 운영진님(스파르타코딩클럽 대표)이 첫 날 하신 말씀은 일요일은 쉬어라였다.

하지만, 마음놓고 마냥 쉬기에는 몸이 쳐질 것같고 나태함의 맛에 빠져 헤어나올 수 없을 것같았다.

하지만, 월요일~토요일보다는 1시간 더 자고 쌓인 피로감을 풀어주었다.

그리고 오늘부터 구운계란 2개와 견과류 1봉지를 챙겨 먹기 시작했다.

운동을 할 시간을 따로 낼 만큼 여유롭다고 생각하지 않기에 3끼를 챙겨먹으며 간간히 산책을 하며 건강을 챙길 생각이다.

건강을 유지하며 목표로 했던 것을 이루기 위해 내일도 달려야한다.

 

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)