1. 정렬 알고리즘

정렬 알고리즘

알고리즘	평균	최악	기법	특징
버블 정렬	O(n^2)	O(n^2)	비교, 교환	쉬움
카운팅 정렬	O(n+k)	O(n+k)	비교환	n이 작을때만, k는 정수의 최대값
선택 정렬	O(n^2)	O(n^2)	비교, 교환	교환 수가 버블, 삽입 보다 적음
퀵 정렬	O(n logn)	O(n^2)	분할 정복	평균적으로 가장 빠름
삽입 정렬	O(n^2)	O(n^2)	비교, 교환	n의 개수가 작을 때 효과적
병합 정렬	O(n logn)	O(n logn)	분할 정복	링크드리스트의 경우 가장 효율적
힙 정렬	O(n logn)	O(n logn)	힙 자료구조

---

 

버블 정렬

• 첫 번째 원소부터 인접한 원소끼리 자리를 교환하면서 맨 마지막 자리까지 이동
• 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 이동됨

버블 정렬

def BubbleSort(list):
    n = len(list)
    for _ in range(n):
        for j in range(n-1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]
                
    return list

 

 

카운팅 정렬

• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
• 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 리스트를 사용하기 때문
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수 k를 알아야 함
• n이 커질수록 추가적인 메모리 낭비가 커지므로, n이 작을때만 사용이 가능

카운팅 정렬

def CountingSort(list, k):
    n = len(list)
    count_list = [0]*(k+1)  # 최댓값 k 크기의 카운팅 리스트
    sorted_list = [-1]*n    # 정렬된 결과 리스트

    # 각 요소가 등장하는 횟수 카운팅
    for elem in list:
        count_list[elem] += 1  # 요소의 값을 카운팅 리스트의 인덱스로 사용하여 횟수 증가

    # 카운팅 리스트 값을 누적 합으로 바꿈
    for i in range(1, k+1):
        count_list[i] += count_list[i-1]

    # 정렬된 리스트 채움
    for i in range(1, n+1):
        id = count_list[list[-i]]  # 요소의 카운팅 값
        sorted_list[id-1] = list[-i]
        count_list[list[-i]] -= 1  # 카운팅 값 -1

    return sorted_list

 

⭐ 이렇게 풀 수도 있어요! 메모리를 더 적게!

2021.08.11 - [Coding Test/백준 (BOJ)] - 백준 10989 - 실버5

백준 10989 - 실버5

 

선택 정렬

• 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
• 즉, 각각의 반복마다 최소값을 찾아 맨 앞의 값과 교환

선택 정렬

def SelectionSort(list):
    n = len(list)

    for i in range(n):
        min = list[i]
        min_id = None
        for j in range(i+1, n):  # 뒤에 리스트 중에서 최소값 찾음
            if list[j] < min:
                min = list[j]
                min_id = j
        if min_id:  # 최소값 발견된 경우
            list[i], list[min_id] = list[min_id], list[i]
    
    return list

 

퀵 정렬

• 리스트를 두 개로 분할하고, 각각의 정렬
• 기준 아이템을 중심으로 작은 것은 왼쪽, 큰 것은 오른쪽에 위치 시킴

퀵 정렬

def quick_sort(A, l, r): # 리스트, 시작 인덱스, 끝 인덱스
    if l < r:
        s = HoarePartition(A, l, r)
        quick_sort(A, l, s-1)
        quick_sort(A, s+1, r)

def HoarePartition(A, l, r): # Hoare
    pivot = A[l]  # 피봇 : 맨앞
    L = l+1
    R = r
    while L <= R:
        while L <= R and A[L] <= pivot:  # pivot 보다 큰 값이 나올 때까지 이동
            L += 1
        while L <= R and A[R] >= pivot:  # pivot 보다 작은 값이 나올 때까지 이동
            R -= 1
        if L <= R:
            A[L], A[R] = A[R], A[L]  # L과 R의 요소 교환
            
    A[l], A[R] = A[R], A[l]  # 마지막에는 pivot과 R을 교환
    return R

⭐ 참고!

파이썬에서 리스트는 가변객체로(mutable object), 함수의 argument로 전달할 때 Call by Reference가 된다.

따라서, 리스트를 리턴하지 않아도 원래 객체가 변경된다.

 

 

삽입 정렬

• 리스트의 두 번째 요소부터 시작
• 앞부분의 리스트는 정렬된 집합으로, 현재 요소가 정렬된 집합에 어느 위치에 들어갈지 결정함
• 교환이 안일어나면 베스트는 O(n)

삽입 정렬

def InsertionSort(list):
    n = len(list)
    
    for end in range(1, n):
        for i in range(end, 0, -1):
            if list[i-1] > list[i]:
                list[i-1], list[i] = list[i], list[i-1]

 

 

병합 정렬

• 자료를 최소 단위의 문제까지 분할하고, 차례대로 정렬
  • Top-Down 방식

병합 정렬

import collections

def merge_sort(m):
    if len(m) <= 1: # 사이즈가 0이거나 1인 경우, 바로 리턴
        return m

    # DIVIDE
    mid = len(m) // 2
    left = m[:mid]
    right = m[mid:]

    # Recursion
    left = merge_sort(left)
    right = merge_sort(right)

    # CONQUER
    return merge(left, right)

def merge(left, right):
    result = [] # 두 리스트를 병합하여 result를 채움
    left = collections.deque(left)  # 시간 효율성을 위해 deque로 변환
    right = collections.deque(right)

    while len(left)>0 and len(right)>0:
        # 두 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가
        if left[0] <= right[0]:
            result.append(left.popleft())
        else:
            result.append(right.popleft())

    # 왼쪽 리스트에 원소 남아있는 경우
    if len(left) > 0:
        result += left
    # 오른쪽 리스트에 원소 남아있는 경우
    if len(right) > 0:
        result += right
    return result

 

힙 정렬

• 최대 힙 트리(내림차순)나 최소 힙 트리(오름차순)를 구성해 정렬하는 방법
  • 정렬할 요소들로 완전 이진 트리 형태인 최대/최소 힙을 만든다.
  • 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다.

 

---

정렬 알고리즘의 비교

• 구현이 간단하지만 비효율적인 방법 : 버블, 카운팅, 선택, 삽입
• 복잡하지만 효율적인 방법 : 퀵, 병합, 힙

 

정렬에서 Stable의 개념

stable 정렬이란 "정렬되지 않은 상태에서 같은 값을 가진 원소의 순서가 정렬 후에도 유지되는 알고리즘"를 의미한다.

• stable 정렬 : 버블, 카운팅, 삽입, 병합
• unstable 정렬 : 선택, 퀵, 힙

 

정렬에서 In-Place의 개념

In-Plcae 정렬이란 "원소들의 개수 N에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 알고리즘"을 의미한다.
정렬을 위한 추가적인 메모리 공간이 거의 안 드는 정렬 알고리즘이라고 생각하면 된다.

• In-Place : 버블, 선택, 퀵, 삽입, 힙
• Not In-Place : 카운팅, 병합