정렬(Sorting) 개념 정리

📖 정렬(Sorting)

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미
• 정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해짐
• 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하면 만들 수 있기 때문에 오름차순을 기준으로 정렬 알고리즘들을 배울 예정

📖 선택 정렬(Selection Sort)

• 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어지는 원리를 이용한 정렬
• 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 함

✏️ 6-1.py 선택 정렬 소스코드

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]

✏️ 6-2.py 파이썬 스와프(Swap) 소스코드

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

[5,3]

📖 선택 정렬의 시간 복잡도

• O(N2)
• 직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있음

데이터의 개수(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)

• 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort) 알고리즘이라고 함
• 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정
• 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적임
• 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 특징이 있음
• 따라서 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 됨

✏️ 6-3.py 삽입 정렬 소스 코드

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):
    
    	# 정렬하고자 하는 원소보다 앞에 있는 원소가 더 크다면 자리 바꾸기
    	if array[j] < array[j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
            
        # 정렬하고자 하는 원소보다 앞에 있는 원소가 더 작다면 이동을 멈추기
        else:
        	break
            
print(array)

📖 삽입 정렬의 시간 복잡도

• O(N2)
• 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었기 때문
• 최선의 경우 O(N)의 시작 복잡도를 가짐
• 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있음

📖 퀵 정렬(Quick Sort)

• 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
• 퀵 정렬에서는 피벗(Pivot)이 사용됨
  • 피벗이란 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 의미
  • 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정함

📖 퀵 정렬 알고리즘
(1) 리스트에서 첫 번째 데이터를 피벗으로 설정
(2) 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾음
(3) 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해줌
(4) 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행됨

📖 재귀 함수로 구현한 퀵 정렬

• 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해짐
• 재귀 함수로 작성하였을 때 퀵 정렬이 끝나는 조건은, 바로 현재 리스트의 데이터 개수가 1개인 경우임

✏️ 6-4.py 퀵 정렬 소스 코드

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

def quick_sort(array, start, end):

	# 원소가 1개인 경우 종료
	if start >= end:
    	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)

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

✏️ 6-5.py 파이썬의 장점을 살린 퀵 정렬 소스코드

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(NlogN) (일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미)
• 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편임

데이터의 개수(N)	N2(선택 정렬, 삽입정렬)	Nlog2N(퀵 정렬)
N = 1,000	≈ 1,000,000	≈ 10,000
N = 1,000,000	≈ 1,000,000,000,000	≈ 20,000,000

• 평균적으로 시간 복잡도가 O(NlogN) 이지만 최악의 경우 시간 복잡도가 O(N2) 임
• 데이터가 무작위로 입력되는 경우 퀵 정렬이 빠르게 동작할 확률이 높지만, 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작함
• 삽입 정렬은 이미 데이터가 정렬되어 있는 경우 매우 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다고 이해할 수 있음
• 참고로, 파이썬 기본 정렬 라이브러리를 이용하면 O(NlogN) 을 보장함

📖 계수 정렬(Count Sort)

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N + K) 를 보장
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있음
• 다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없음

📖 계수 정렬 알고리즘
(1) 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성
(2) 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료됨

✏️ 6-6.py 계수 정렬 소스코드

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

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

📖 계수 정렬의 시간 복잡도

• O(N + K)
• 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문
• 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있음

📖 계수 정렬의 공간 복잡도

• O(N + K)
• 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없음
• 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리함

📖 파이썬의 정렬 라이브러리

• 정렬 알고리즘 문제는 어느 정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있음
• 알고리즘 문제에서는 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 더 효과적인 경우가 많음
• 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공
• sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN) 을 보장한다는 특징이 있음

✏️ 6-7.py sorted 소스코드

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

result = sorted(array)
print(result)

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

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

✏️ 6-8.py sort 소스코드

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

array.sort()
print(array)

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

• 또한 sorted()나 sort()를 이용할 때에는 key 매개변수를 입력받을 수 있음
• key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 됨

✏️ 6-9.py 정렬 라이브러리에서 key를 활용한 소스코드

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

def setting(data):
	return data[1]

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

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

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

• 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN) 을 보장함
• 앞서 파이썬은 병합 정렬에 기반한다고 했지만 정확히는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있음

(1) 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
(2) 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
(3) 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.