이론
정렬이란?
데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
프로그램에서는 데이터를 사용할 때 오름차 또는 내림차순으로 정렬해서 사용하는 경우가 많다. 정렬 알고리즘으로 이진 탐색의 전처리 과정이기도 하다,
많이 사용하는 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있다.
아래의 카드를 정렬해보며 다양한 정렬 알고리즘에 대해 알아보자. 데이터의 개수는 N으로 표현하며, 현재 N=10이다.
선택 정렬
선택 정렬(Selection Sort)은 무작위로 여러 개 있는 데이터 중 가장 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것이다. 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다.
위 예시에서 빨간색은 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터, 주황색은 이미 정렬된 데이터, 초록색은 현재 확인 중인 데이터를 의미한다. 현재 정렬되지 않은 데이터 중 가장 작은 값을 찾아 앞으로 보내는 과정을 9번 반복한다.
즉, 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr)
시간 복잡도
선택 정렬은 N-1번 가장 작은 수를 찾아 맨 앞으로 보내야 하며, 매번 가장 작은 수를 찾기 위한 비교 연산이 필요하다. 이는 N + (N-1) + ... + 2 번의 연산 수행, 근사치로 N * (N+1) / 2번의 연산이 수행되며 간단히 O(N^2)의 시간 복잡도로 표현할 수 있다.
선택 정렬은 다른 정렬 알고리즘이나 파이썬의 기본 정렬 라이브러리에 비해 매우 비효율적이다. 그러나 리스트에서 가장 작은 데이터를 찾는 일이 코테에서 잦게 있으므로 해당 코드 형태에 익숙해지는 것이 좋다. 선택 정렬 코드를 자주 작성해보자!
삽입 정렬
삽입 정렬(Insertion Sort)은 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입한다.
주황색 데이터는 정렬이 완료된 데이터, 빨간색 데이터는 삽입할 데이터, 초록색은 현재 비교 중인 데이터이다. 삽입 정렬에서 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두 번째 데이터부터 시작한다. 특정 데이터를 다른 데이터들과 비교하여 적절한 위치에 삽입하는 과정을 N-1번 반복하면 모든 데이터가 정렬된다.
삽입 정렬에서 정렬이 이루어지면 항상 오름차순을 유지하고 있기 때문에, 특정 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈춘다. 그 왼쪽의 데이터들은 이미 정렬된 상태기 때문에 더 이상 데이터를 살펴볼 필요가 없다.
코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j]
else:
break
print(arr)
시간 복잡도
삽입 정렬의 시간 복잡도는 O(N^2)으로 선택 정렬과 마찬가지로 반복문이 2중으로 중첩되어 사용되었다. 하지만 만약 정렬해야할 리스트가 거의 정렬되어 있는 상황이라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가지므로 거의 정렬되어 있는 상태로 입력이 주어진다면 삽입 정렬을 이용하는 것이 유리하다. 퀵 정렬과 비교했을 때 보통의 경우엔 삽입 정렬이 더 비효율적이지만, 정렬이 거의 되어 있는 상황에서는 퀵 정렬보다 삽입 정렬이 더욱 빠르게 동작한다.
퀵 정렬
퀵 정렬(Quick Sort)은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것이다. 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피벗(Pivot)이 사용되고, 이는 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 기준을 의미한다.
퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 방식으로 퀵 정렬을 구분하는데 호어 분할(Hoare Partition) 방식을 기준으로 퀵 정렬을 알아보자. 호어 분할 방식에서는 "리스트에서 첫 번째 데이터를 피벗으로 정한다"는 규칙에 따라 피벗을 설정한다.
이렇게 피벗을 설정한 뒤에는 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다. 이 과정을 반복하면 ```피벗```에 대한 정렬이 수행된다.
[1] 리스트의 첫 번째 데이터를 피벗으로 설정한다. (5) 이후 왼쪽부터 5보다 큰 데이터를 선택하므로 7 선택, 오른쪽부터 5보다 작은 데이터를 선택하므로 4 선택. 두 데이터의 위치를 교환한다.
[2] 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾아서 위치를 변경한다. 9와 2.
[3] 이 과정을 반복하다 왼쪽에서부터 찾는 값과 오른쪽부터 찾는 값의 위치가 서로 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 1과 5
[4] 피벗 5에 대해서 분할이 완료되었다. 5 왼쪽의 데이터는 모두 5보다 작고, 오른쪽의 데이터는 모두 5보다 크다. 이러한 작업을 분할 또는 파티션이라고 한다.
[5] 왼쪽 리스트와 오른쪽 리스트 각각에 대해 퀵 정렬을 동일하게 수행한다.
이 과정에서 재귀 함수와 동작 원리가 같고, 실제 코드에서 재귀 함수를 사용해 구현한다. 퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개면 이미 정렬되어 있다고 간주할 수 있고, 더이상 분할이 불가능하다.
코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 피벗은 첫 번째 원소
left = start+1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and arr[left] <= arr[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right >= start and arr[right] >= arr[pivot]:
right -= 1
if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
arr[left], arr[right] = arr[right], arr[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(arr, start, right-1)
quick_sort(arr, right+1, end)
quick_sort(arr, 0, len(arr)-1)
print(arr)
파이썬의 장점을 살린 코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr):
if len(arr) <= 1: # 리스트가 하나 이하의 원소를 담고 있다면 종료
return arr
pivot = arr[0] # 피벗은 첫 번째 원소
tail = arr[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(arr))시간 복잡도
퀵 정렬의 편균 시간 복잡도는 O(NlogN)이다. 선택 정렬과 삽입 정렬에 비해 매우 빠르다. 데이터의 개수가 많을수록 차이는 극명하게 드러난다.
그러나 최악의 경우 시간 복잡도가 O(N^2)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높지만, 이미 데이터가 정렬되어 있는 경우에는 느리게 동작한다. 삽입 정렬과 반대된다고 이해할 수 있다.
참고 시뮬레이션 (약간 다른 방식)
계수 정렬
계수 정렬(Count Sort)은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르다. 다만, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 만약 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 계수 정렬이 이러한 특징을 가지는 이유는 '모든 범위를 담을 수 있는 크기의 리스트'를 선언해야 하기 때문이다. 계수 정렬은 비교 기반의 정렬 알고리즘이 아니며, 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다. 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터이ㅡ 개수가 매우 많더라도 빠르게 동작하므로, 많은 데이터가 존재하는 경우를 살펴보자.
먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 위의 예시에서는 0~9로 크기가 10인 리스트를 선언하고 0으로 초기화한다. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록되고, 리스트의 첫 번째 데이터부터 그 값만큼 인덱스를 출력하면 정렬된 결과를 확인할 수 있다.
코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(arr) + 1)
for i in range(len(arr)):
count[arr[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
공간 복잡도
계수 정렬은 때에 따라 매우 비효율적일 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 존재하는 경우에도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
파이썬의 정렬 라이브러리
sorted()와 sort() 함수 사용
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(sorted(arr)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(arr) # [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
arr.sort()
print(arr) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
key 매개변수를 이용해 정렬 기준을 설정할 수 있다. key 값으로는 하나의 함수가 들어가야 한다.
arr = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data):
return data[1]
result = sorted(arr, key=setting)
print(result)
정렬 라이브러리는 이미 잘 작성된 함수이므로 직접 퀵 정렬을 구현할 때보다 더욱 효과적이다. 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
문제에서 별도의 요구가 없이 단순히 정렬해야 하는 상황에선 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 하는 경우 계수 정렬을 사용해보자.
코테에서 정렬 알고리즘이 사용되는 경우 3가지
1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
3. 더 빠른 정렬이 필요한 문제
실전 문제
실전 문제 2. 위에서 아래로
n = int(input())
arr = [0] * n
for i in range(n):
arr[i] = int(input())
result = sorted(arr, reverse=True)
for r in result:
print(r, end=' ')
실전 문제 3. 성적이 낮은 순서로 학생 출력하기
n = int(input())
arr = []
for _ in range(n):
temp = input().split()
arr.append([temp[0], int(temp[1])])
arr = sorted(arr, key= lambda student: student[1])
for student in arr:
print(student[0], end=' ')
실전 문제 4. 두 배열의 원소 교체
n,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
for i in range(k):
if a[i] < b[i]:
a[i],b[i] = b[i],a[i]
else:
break
print(sum(a))
출처
이것이 코딩 테스트다
https://visualgo.net/en/sorting