알고리즘: 정렬

정렬 방식

자주 사용하는 정렬 방식은 크게 2가지로 나눌 수 있다. 첫 번째로 2중 반복문을 사용하는 Bubble, Select, Insert 정렬이다. 두 번째는 분할-정복 방법을 사용하는 병합, 퀵 정렬이다.

 

2중 반복문을 사용하는 정렬 방식

해당 방식은 최악의 경우 시간복잡도는 O(N^2)이 된다.

이와 같은 이유는 2개의 반복문을 통해 값을 비교하기 때문이다.

Bubble Sort

서로 인접한 두 원소를 검사하여 정렬하는 방식을 사용한다. swap이 더 이상 발생하지 않으면, 중단하여 불필요한 반복문을 실행하지 않을 수 있다.

 

    def bubble_sort(nums):
        for i in range(len(nums)):
            swap = False
            for j in range(1, len(nums)):
                if nums[j - 1] > nums[j]:
                    nums[j - 1], nums[j] = nums[j], nums[j - 1]
                    swap = True
            if not swap:
                break
    

 

Select Sort

정렬 하고자 하는 값들 이외에 추가적인 공간을 필요로 하지 않는 in-place 정렬하는 방식을 사용한다. 말그대로 첫 번째 원소부터 선택하고, 가장 작은 값을 탐색하여 맨 앞의 위치로 갈 수 있도록 하는 방식이다.

 

def select_sort(num):
    for i in range(len(num)):
        min_idx = i
        for j in range(i + 1, len(num)):
            if num[min_idx] > num[j]:
                min_idx = j
        num[i], num[min_idx] = num[min_idx], num[i]

 

Insert Sort

원소의 값을 비교하여 해당 원소를 적절한 위치에 삽입하여 정렬하는 방식이다. Bubble, Select와 달리 라운드가 진행할 수록 비교 대상이 증가한다.

 

def insert_sort(num):
    for i in range(len(num)):
        key = num[i]
        j = i - 1
        while j >= 0 and key < num[j]:
            num[j+1] = num[j]
            j -= 1
            num[j+1] = key

 

---

 

분할-정복을 사용하는 정렬 방식

2중 반복문 보다 효율적으로 정렬할 수 있는 방식이며, 큰 문제를 작은 문제로 나누어 단계적으로 해결하는 방식이라고 하여 분할-정복이라고 표현한다.

 

Merge Sort

배열을 반으로 나누어 left, right를 각각 재귀 호출을 통해 처리하게 되며, 더 이상 나누어지지 않게 되면 값이 반환되어 정렬되는 방식을 사용한다.

 

def merge_sort(num):
    length = len(num)
    if length <= 1:
        return

    mid = length // 2
    left = num[:mid]
    right = num[mid:]
    merge_sort(left)
    merge_sort(right)
    # left index
    i = 0
    # right index
    j = 0
    # num list index
    k = 0
    # left, right의 값을 비교하여 원래 배열에 값을 정렬함
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            num[k] = left[i]
            i += 1
        else :
            num[k] = right[j]
            j += 1
        k += 1
	# 대소비교가 되지 않은 나머지 값들을 넣음
    while i < len(left):
        num[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        num[k] = right[j]
        j += 1
        k += 1

 

Quick Sort

기준 값을 정하여 원소와 기준 값을 비교 후 값이 작으면 less로 크면 more로 분류하여 정렬을 하는 방식이다.

 

def quick_sort(num):
    length = len(num)
    if length <= 1:
        return num

    pivot = num[0]
    less = []
    more = []
    for i in range(1, len(num)):
        if num[i] < pivot:
            less.append(num[i])
        else:
            more.append(num[i])
    return quick_sort(less) + [pivot] + quick_sort(more)