[정렬] 기준에 따라 데이터를 정렬

연두·2021년 6월 27일

알고리즘 정렬

이코테

목록 보기

6/9

정렬 (Sorting)

데이터를 특정한 기준에 따라 순서대로 나열하는 것

선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬과 정렬 라이브러리에 대한 정리!

1. 선택 정렬 (Selection Sort)

매번 가장 작은 것을 선택하는 알고리즘

선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하는 것이다.

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)

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

선택 정렬의 시간 복잡도
$o\left(N^2\right)$

다른 알고리즘과 비교했을 때 매우 비효율적이지만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.

2. 삽입 정렬 (Insertion Sort)

특정한 데이터를 적절한 위치에 삽입하는 알고리즘

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다. 영상을 보시면 더 이해가 잘 될 것이다.

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)

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도
$o\left(N^2\right)$

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

(최선의 경우 O(N) 의 시간 복잡도)

3. 퀵 정렬 (Quick Sort)

기준(피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작하는 알고리즘

퀵 정렬에서는 피벗(Pivot)이 사용된다. 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'이다.
리스트에서 첫 번째 데이터를 피벗으로 정하는 호어 분할(Hoare Partition) 방식을 사용한다.
피벗을 설정한 뒤에는 왼쪽에서 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다.
그 다음 큰 데이터와 작은 데이터의 위치를 교환해 준다.

이러한 방법을 반복한다.

이렇게 분할(Divide)이 완료되면, 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치한다.
그 다음 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 이는 재귀함수와 동작 원리가 같다.

리스트의 데이터 개수가 1개인 경우 종료하는 재귀함수를 사용한다.

(영상 참고!)

파이썬으로 작성한 퀵 정렬 소스코드

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복 
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

파이썬의 장점을 살린 퀵 정렬 소스코드

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))

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬의 시간 복잡도
$O\left(N\log N\right)$

퀵 정렬은 앞서 다룬 두 알고리즘에 비해 매우 빠른 편이다.
하지만, '이미 데이터가 정렬되어 있는 경우' 에는 매우 느리게 동작한다.

4. 계수 정렬 (Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만
매우 빠른 알고리즘
계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있어요.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
계수 정렬은 비교 기반의 정렬 알고리즘이 아니다.

계수 정렬

① 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
② 리스트의 모든 데이터가 0이 되도록 초기화한다.
③ 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

계수 정렬의 시간 복잡도

데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때,
$O\left(N+K\right)$

계수 정렬의 공간 복잡도
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
데이터 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

파이썬의 정렬 라이브러리

파이썬의 정렬 라이브러리
🔗 sorted(), sort()

정렬 라이브러리의 시간 복잡도
정렬 라이브러리는 항상 최악의 경우에도
$O\left(N\log N\right)$
의 시간 복잡도를 보장한다.
문제에서 별도의 요구가 없다면 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하면 된다.

<코딩테스트의 일반적인 3가지 문제유형>
① 정렬 라이브러리로 풀 수 있는 문제 : 정렬 라이브러리 사용
② 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고있어야 함
③ 더 빠른 정렬이 필요한 문제 : 계수 정렬 등의 다른 정렬 알고리즘 사용 or 문제에서 기존에 알려진 알고리즘을 구조적으로 개선해야 함

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O ( N^2 )	O ( N )	아이디어가 매우 간단
삽입 정렬	O ( N^2 )	O ( N )	데이터가 거의 정렬되어 있을 때 가장 빠름
퀵 정렬	O ( N log N )	O ( N )	대부분의 경우에 가장 적합, 충분히 빠름
계수 정렬	O ( N + K )	O ( N + K )	데이터의 크기가 한정되어 있는 경우에만 사용하지만 매우 빠르게 동작