[정렬 알고리즘] 기준에 따라 데이터를 정렬

정렬 알고리즘

- 정렬 (Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐

- 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 됨

 

정렬 라이브러리

- 현대의 정렬 알고리즘은 정립되어 있기 때문에 앞으로 큰 개선이 이루어질 것이라고 예상하기는 어려움

- 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제

- 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 많음

 

정렬 라이브러리의 시간 복잡도

- 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장

- 정렬 라이브러리는 이미 잘 작성된 함수이므로 직접 퀵 정렬을 구현할 때보다 더욱 효과적

- 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용

- 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용

 

정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있음

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있음

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있음

 

 

선택 정렬

- 데이터가 무작위로 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정

- 가장 원시적인 방법으로 '매번 가장 작은 것을 선택'한다는 의미

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array)

 

선택 정렬의 시간 복잡도

- 선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함

- 또한 매번 가장 작은 수를 찾기 위하여 비교 연산이 필요

- 선택 정렬의 시간 복잡도는 O(N^2) (직관적으로 간단한 형태의 2중 반복문이 사용되었기 때문)

- 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려짐

- 선택 정렬은 매우 비효율적이지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 잦으므로 익숙해져야함

 

삽입 정렬

- 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘

- 선택 정렬에 비해 구현 난이도가 높지만 실행 시간 측면에서 더 효율적

- 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적

- 특정한 데이터를 적절한 위치에 '삽입'한다는 의미

- 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정

- 삽입 정렬은 두 번째 데이터부터 시작 (이유는 첫 데이터는 그 자체로 정렬되어 있다고 판단)

- 정렬이 이루어진 원소는 항상 오름차순을 유지

- 특정한 데이터가 삽입될 위치를 선정할 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 정지

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

삽입 정렬의 시간 복잡도

- 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 O(N^2)

- 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요

- 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 (최선의 경우 O(N)의 시간 복잡도)

- 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력

 

퀵 정렬

- 가장 많이 사용되는 알고리즘

- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작

- 원리를 이해하면 다른 고급 정렬 기법에 비해 쉽게 소스 코드를 작성 가능

- 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 피벗이라 하는데, 퀵 정렬은 피벗을 사용

- 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 함

- 가장 대표적인 분할 방식인 '호어 분할' 방식을 기준으로 설명함

 

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

퀵 정렬의 시간 복잡도

- 퀵 정렬의 평균 시간 복잡도는 O(NlogN) (앞서 다루었던 두 알고리즘에 비해 매우 빠른 편)

- 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2)

- 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작 (삽입 정렬과 반대)

- 기본 정렬 라이브러리를 이용하면 O(NlogN)을 보장해줌

 

계수 정렬

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

- '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능

- 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어려움

- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능

- '모든 범위를 담을 수 있는 크기의 리스트'를 선언해야 하기 때문

- 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤 위치를 변경하며 정렬하는 방식이 아님

 

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

 

계수 정렬의 시간 복잡도

- 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)

- 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시키고, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문

- 데이터의 범위만 한정되어 있다면 효과적으로 사용 가능 (항상 빠르게 동작)

- 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠름

 

계수 정렬의 공간 복잡도

- 때에 따라서 심각한 비효율성을 초래

- 데이터가 0과 999,999 단 2개만 존재할 때에도 리스트의 크기가 100만 개가 되도록 선언해야 함

- 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합

- 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리

- 조건만 만족한다면 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용 가능

- 일반적인 코딩 테스트의 시스템 환경에서는 메모리의 공간상의 제약과 입출력 시간 문제로 인해 공간 복잡도는 O(N+K)임