[알고리즘] 정렬 (선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 정렬 라이브러리)

본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다.

독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다.

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

• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 (Binary Search)이 가능해진다.
  • 정렬 알고리즘은 이진 탐색의 전처리 과정이다.

선택 정렬 (Selection Sort)

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
• 회색 카드 : 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터
• 하늘색 카드 : 이미 정렬된 데이터

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

for i in range(len(array)): # i는 가장 작은 데이터가 위치가 바뀐 인덱스 (매번 앞쪽으로 보내고자 하는 가장 앞쪽 원소) 
    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)

[실행 결과]

Swap (스와프) : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
  • $N + (N - 1) + (N - 2) + ... + 2$
  • 가장 마지막 원소는 정렬을 수행해주지 않아도 괜찮기 때문에 2로 생각
• 이는 근사치로 $(N^2 + N - 2) / 2$로 표현할 수 있는데, 빅오 표기법에 따라서 $O(N^2)$라고 작성한다.
• 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다.

데이터의 개수 (N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123초	0.00156초	0.00000753초
N = 1,000	0.354초	0.00343초	0.0000365초
n = 10,000	15.475초	0.0312초	0.000248초

삽입 정렬 (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까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break


print(array)

[실행 결과]

• 삽입 정렬의 시간 복잡도는 $O(N^2)$이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
  • 최선의 경우 $O(N)$의 시간 복잡도를 가진다.
• 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

퀵 정렬 (Hore Partition)

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
• 아래는 가장 대표적인 분할 방식인 호어 분할(Hore Partition) 방식을 기준으로 설명한 규칙이다.

• 퀵 정렬이 빠른 이유
  • 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 $O(NlogN)$를 기대할 수 있다.
  • 너비 X 높이 = $ N time logN = NlogN$
    

    

• 퀵 정렬을 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다.
  • 재귀 함수와 동작 원리가 같다면, 종료 조건도 있어야 한다.
  • 퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 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)

[실행 결과]

• 퀵 정렬은 평균의 경우 $O(NlogN)$의 시간 복잡도를 가진다.

  데이터의 개수(N)	$N^2$(선택 정렬, 삽입 정렬)	$Nlog_2N$(퀵 정렬)
  N = 1,000	1,000,000	10,000
  N = 1,000,000	1,000,000,000,000	20,000

• 하지만 최악의 경우 $O(N^2)$의 시간 복잡도를 가진다.
  
  • 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행한다면?
    

    

  • 매번 분할이 이루어질 때마다 오른쪽 데이터만 남기 때문에 분할이 수행되는 횟수가 N과 비례, 분할을 하기 위해서 매번 선형 탐색을 수행해야하기에 $O(N^2)$의 시간 복잡도를 가진다.
• 따라서 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다.

[파이썬의 장점을 살린 퀵 정렬 소스코드 with List Slicing, List Comprehension]

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

[실행 결과]

계수 정렬 (Count Sort)

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
  • 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
  • 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
  • 계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문이다.
• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 $O(N + K)$를 보장한다.

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

[실행 결과]

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 $O(N + K)$이다.
  • 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
  • 데이터가 0과 999,999로 단 2개만 존재하는 경우를 생각해 보자.
  • 이럴 경우에도 리스트의 크기가 1000만개가 되도록 선언해야 한다.
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
  • 성적의 경우 100점을 맞은 학생이 여려명 있을 수 있기 때문에 계수 정렬이 효과적이다.
• 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다. 

정렬 알고리즘 비교하기

• 앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다.
• 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 $O(NlogN)$을 보장하도록 설계되어 있다.

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

파이썬의 정렬 라이브러리

• sorted()
  • 퀵 정렬과 동작 방식이 비슷한 병합 정렬 기반
  • 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다.
  • 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.

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

result = sorted(array)
print(result)

[실행 결과]

• sort()
  • 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수 있다.
  • 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

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

array.sort()
print(array)

[실행 결과]

• key 매개변수를 활용
  • sorted()나 sort()를 이용할 떄에는 key 매개변수를 입력으로 받을 수 있다.
  • key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된더.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key = setting)
print(result)

[실행 결과]

[선택 정렬과 기본 정렬 라이브러리 수행 시간 비교]

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    # 1부터 100 사이의 랜덤한 정수
    array.append(randint(1, 100))
    
# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
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]
    
# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("선택 정렬 성능 측정:", end_time - start_time)

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    # 1부터 100 사이의 랜덤한 정수
    array.append(randint(1, 100))
    
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time)

[실행 결과]

• 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다.
• 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.
• 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.
• 코딩 테스트에서 정렬 알고리즘이 사용되는 경우
  1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
  2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
  3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

Example 1) 위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

[입력 조건]

• 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 ≤ N ≤ 500)
• 둘째 줄부터 N + 1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

[출력 조건]

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다.

[Solution]

• 가장 기본적인 정렬을 할 수 있는지 물어보는 문제이다.
• 모든 수는 1 이상 100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있다.
• 가장 코드가 간결해지는 파이썬의 기본 정렬 라이브러리를 이용하는 것이 효과적이다.

# N을 입력받기
n = int(input())

# N개의 정수를 입력받아 리스트에 저장
array = []
for i in range(n):
    array.append(int(input()))

# 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행
array = sorted(array, reverse = True)

# 정렬이 수행된 결과를 출력
for i in array:
    print(i, end = ' ')

[실행 결과]

Example 2) 성적이 낮은 순서로 학생 출력하기

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

[입력 조건]

• 첫 번째 줄에 학생의 수 N이 입력된다. (1 ≤ N ≤ 100,000)
• 두 번째 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

[출력 조건]

• 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

[Solution]

• 학생의 정보가 최대 100,0000개까지 입력될 수 있으므로 최악의 경우 $O(NlgoN)$을 보장하는 알고리즘을 이용하거나 $O(N)$을 보장하는 계수 정렬을 이용하면 된다. 
• 입력되는 데이터는 학생의 이름과 점수지만 출력할 때는 학생의 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행해야 한다.

# N을 입력받기
n = int(input())

# N명의 학생 정보를 입력받아 리스트에 저장
array = []
for i in range(n):
    input_data = input().split()
    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
    array.append((input_data[0], int(input_data[1])))

# 키(Key)를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])

# 정렬이 수행된 결과를 출력
for student in array:
    print(student[0], end = ' ')

[실행 결과]

Example 3) 두 배열의 원소 교체

동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.

N, K, 그리고 배열 A, B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

[입력 조건]

• 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 ≤ N ≤ 100,000 ≤ K ≤ N)
• 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
• 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

[출력 조건]

•  최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

[Solution]

• 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다.
  • 단 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 한다.
• 이러한 과정을 K번 반복면 원하는 정답을 얻을 수 있다. 
• 따라서 배열 A와 B의 정보가 입력되면 배열 A의 원소는 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 정렬하여 두 배열의 원소를 가장 첫 번째 인덱스부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다. 
• 두 배열의 원소가 최대 100,000개 까지 입력될 수 있으므로 $O(NlogN)$을 보장하는 정렬 알고리즘을 이용해야 한다.

n, k = map(int, input().split())    # N과 K를 입력받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기
b = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기

a.sort() # 배열 A는 오름차순으로 정렬
b.sort(reverse = True) # 배열 B는 내림차순으로 정렬

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        break

print(sum(a)) # 배열 A의 모든 원소의 합을 출력

[실행 결과]