[알고리즘 코테] 정렬

대표적인 정렬의 종류

1) O(n²)의 시간 복잡도 

• 버블 정렬(Bubble Sort) : 바로 옆에 있는 것과 비교해서 정렬함. 구현은 쉽지만 효율성이 매우 낮다고 알려짐.
• 선택 정렬(Selection Sort) : 가장 작은 데이터를 선택해서 정렬되지 않은 데이터 중 가장 앞 쪽에 있는 데이터와 위치를 바꾸는 방법
• 삽입 정렬(Insertion Sort) : 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 삽입하는 방법

2) O(n log n)의 시간 복잡도 : divide and conquer

• 합병 정렬, 병합 정렬(Merge Sort) 
• 퀵 정렬(Quick Sort) : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법, 최악의 경우는 O(n²)이지만 평균적으로 O(n log n)
• 힙 정렬(Heap Sort) : 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성함.
  • 힙이란? (최소 힙 기준)
    • 부모 노드의 키가 자식 노드의 키보다 작게 구성된 완전 이진 트리, 중복 값을 허용함.
  • 파이썬의 heapq 모듈을 통해 사용 가능
  • heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공
    • heapq.heapify(heap) : 이미 원소가 들어있는 리스트 → 힙 구조로 재구성, O(n)
    • heapq.heappop(heap) : 힙의 가장 작은 원소를 삭제 후에 그 값을 리턴함. O(log n)
    • heapq.heappush(heap, element) : 힙에 원소를 추가함. O(log n) 
  • 최대 힙
    • 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용

# 최대 힙 만들기
from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heappop(heap)[1])  # index 1

정렬 알고리즘 평균 시간 복잡도 및 공간 복잡도 특징

정렬 알고리즘	시간복잡도	공간복잡도	특징
선택 정렬	O(n²)	O(n)	아이디어가 간단하나, 효율은 낮음.
삽입 정렬	O(n²)	O(n)	데이터가 거의 정렬되어 있을 때는 가장 빠름.
퀵 정렬	O(n log n)	O(n)	대부분의 경우 가장 적합, 충분히 빠름.
계수 정렬	O(n + k)	O(n + k)	특정한 값을 가지는 데이터의 개수를 카운트하는 방법 데이터의 크기가 한정되어 있는 경우에만 사용이 가능, 매우 빠르게 동작

 

import random

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


    def selection_sort(arr):
        for i in range(len(arr)):
            min_index = i
            for j in range(i+1, len(arr)):
                if arr[min_index] > arr[j]:
                    min_index = j
            arr[i], arr[min_index] = arr[min_index], arr[i]
        return arr


    def quick_sort(arr):
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]
        left, right, equal = [], [], []
        for i in arr:
            if i < pivot:
                left.append(i)
            elif i > pivot:
                right.append(i)
            else:
                equal.append(i)
        return quick_sort(left) + equal + quick_sort(right)


    def merge_sort(arr):
        if len(arr) < 2:
            return arr
        
        mid = len(arr) // 2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])

        merged_arr = []
        l = r = 0
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                merged_arr.append(left[l])
                l += 1
            else:
                merged_arr.append(right[r])
                r += 1

        merged_arr += left[l:]
        merged_arr += right[r:]
        return merged_arr


    def heap_sort(arr):
        def heapify(arr, n, i):
            largest = i
            l = 2 * i + 1
            r = 2 * i + 2

            if l < n and arr[i] < arr[l]:
                largest = l

            if r < n and arr[largest] < arr[r]:
                largest = r

            if largest != i:
                arr[i], arr[largest] = arr[largest], arr[i]
                heapify(arr, n, largest)

        n = len(arr)
        for i in range(n, -1, -1):
            heapify(arr, n, i)

        for i in range(n-1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]
            heapify(arr, i, 0)

        return arr



    def radix_sort(arr):
        RADIX = 10
        placement = 1

        max_digit = max(arr)

        while placement < max_digit:
            buckets = [list() for _ in range(RADIX)]

            for i in arr:
                tmp = int((i / placement) % RADIX)
                buckets[tmp].append(i)

            a = 0
            for b in range(RADIX):
                buck = buckets[b]
                for i in buck:
                    arr[a] = i
                    a += 1

            placement *= RADIX

        return arr


    def counting_sort(arr):
        max_value = max(arr)
        m = max_value + 1
        count = [0] * m

        for a in arr:
            count[a] += 1

        i = 0
        for a in range(m):
            for c in range(count[a]):
                arr[i] = a
                i += 1
        return arr


arr = [i for i in random.sample(range(10), 10)]

print("Original array: ", arr)
print("Bubble sort: ", Sort.bubble_sort(arr))
print("Selection sort: ", Sort.selection_sort(arr))
print("Quick sort: ", Sort.quick_sort(arr))
print("Merge sort: ", Sort.merge_sort(arr))
print("Heap sort: ", Sort.heap_sort(arr))
print("Radix sort: ", Sort.radix_sort(arr))
print("Counting sort: ", Sort.counting_sort(arr))

 

파이썬의 정렬 알고리즘

list.sort()
sorted(list)

 

• list.sort() : 입력값으로는 리스트 밖에 받지 못함. 리스트 원본 값을 직접 수정함. 원본이 필요없을 때는 시간, 공간 절약함.
• sorted(list) : 내장함수로 리스트 원본 값은 그대로 유지함. 어떤 입력값이든 받을 수 있음. 원본을 유지해야 할 때 사용함.
  •  Timesort 알고리즘 : 삽입 정렬과 병합 정렬을 결합한 Hybrid stable sorting 알고리즘으로 어느 정도 정렬된 부분이 존재하는 실생활 데이터의 특성을 고려해 더 빠르게 작동하도록 고안한 알고리즘
  • 최선 : O(n), 평균 및 최악 : O(n log n)