정렬 알고리즘 (선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬)
정렬
- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능 / 정렬 알고리즘은 이진 탐색의 전처리 과정
정렬 알고리즘의 종류
- 선택 정렬
- 삽입 정렬
- 퀵 정렬
선택 정렬
- 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
10개의 데이터 예시에 선택 정렬 알고리즘 적용
1. 초기 단계에서 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다.
따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다.
2. 정렬된 데이터를 제외한 데이터 중에서 가장 작은 데이터를 처리되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾸며 정렬되지 않은 데이터가 하나가 남을 때까지 반복한다.
이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 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)
선택 정렬의 시간 복잡도
선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 그림대로 구현했을 때 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다. 따라서 근사치로 N × (N+1) / 2번의 연산을 수행한다고 가정하면 (N**2+N) / 2로 표현할 수 있고 시간 복잡도는 O(N**2)라고 표현할 수 있다.
직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.
선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다. 다만 코딩 테스트에서 특정 리스트의 가장 작은 데이터를 찾는 일이 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.
삽입 정렬
- 삽입 정렬: 특정한 데이터를 적절한 위치에 삽입한다
- 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
- 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.
다음과 같이 초기 데이터가 구성되어 있다고 가정할 때,
삽입 정렬은 두 번째 데이터부터 시작된다. → 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
1. 첫 번째 데이터 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번쨰 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽이나 오른쪽으로 들어가는 두 경우만 존재한다. 오름차순으로 정렬하고자 하므로 '7'의 왼쪽에 삽입한다.
2. 이어서 '9'가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 '9'는 '7'보다 크므로 원래 자리 그대로 둔다.
적절한 위치에 삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬된 것을 확인할 수 있다.
삽입 정렬 소스코드
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)
삽입 정렬의 시간 복잡도
이중 for문으로 O(N**2)이다.
선택 정렬과 흡사한 시간이 소요되지만 삽입 정렬은 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가진다.
퀵 정렬 (가장 많이 사용)
- 퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다.
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
- 퀵 정렬에는 피벗이 사용된다. (피벗: 데이터를 교환할 때의 기준)
퀵 정렬 방법
1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.
2. 왼쪽에서부터 피벗보다 큰 데이터 찾고, 오른쪽에서부터 피벗보다 작은 데이터 찾는다.
3. 두 데이터의 위치를 교환한다.
1. 리스트의 첫 번째 데이터인 '5'를 피벗으로 정한다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택되고 두 데이터의 위치를 교환한다.
2. 다시 왼쪽에서부터 피벗보다 큰 데이터인 '9'를 선택하고, 오른쪽에서부터 피벗보다 작은 데이터인 '2'를 선택하여 위치를 교환한다.
3. 반복하여 진행하다가, 아래와 같이 왼쪽에서부터의 탐색과 오른쪽에서부터의 탐색이 엇갈린 경우, 피벗과 작은 데이터 '1'의 위치를 교환하여 분할을 수행한다.
4. [분할 완료] 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보면 왼쪽 리스트의 데이터는 모두 5보다 작고, 오른쪽 리스트의 데이터는 모두 5보다 크다. 이렇게 위치하도록 하는 작업을 분할 또는 파티션이라고 한다.
왼쪽 리스트 데이터 정렬
왼쪽 리스트의 첫 번째 데이터인 '1'을 피벗으로 놓고 퀵 정렬을 반복한다.
오른쪽 리스트 데이터 정렬
오른쪽 리스트의 첫 번째 데이터인 '6'을 피벗으로 놓고 같은 작업을 반복한다.
퀵 정렬 소스코드
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))
퀵 정렬의 시간 복잡도
퀵 정렬의 평균 시간 복잡도는 O(N log N)이다.
선택 정렬과 삽입 정렬은 최악의 경우에도 시간 복잡도 O(N**2)을 보장하는데 이 두 정렬 알고리즘에 비해 매우 빠르다.
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 모든 데이터가 양의 정수인 상황을 가정할 때 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 O(N+K)를 보장한다.
- 다만, '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
→ 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때에는 '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'해야 하기 때문
- 계수 정렬은 앞서 다룬 3가지 정렬 알고리즘처럼 비교 기반의 정렬 알고리즘이 아니다.
- 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
예를 들어 [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2] 를 정렬할 때,
1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고, 리스트의 모든 데이터를 0으로 초기화한다.
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 값을 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)이다.
데이터 중 최댓값의 크기만큼 반복을 수행하고, 데이터의 범위만 한정되어 있으면 효과적으로 사용할 수 있으며, 항상 빠르게 동작한다.
계수 정렬의 공간 복잡도
- 공간 복잡도 O(N+K)
- 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.
- 데이터 특성 파악하기 어렵다면 퀵 정렬 이용하는 것이 유리하다.
파이썬의 정렬 라이브러리
- 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
- sorted() 함수는 리스트나 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력한다.
- 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.
- sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(N log N)을 보장한다는 특징이 있다.
- sort()나 sorted()를 이용할 때 key 매개변수를 입력으로 받을 수 있는데, key값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.
정렬 라이브러리에서 key를 활용한 소스코드
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)
# [('바나나', 2), ('당근', 3), ('사과', 5)]
정렬 라이브러리의 시간 복잡도
- 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(N log N)을 보장
■ 실전 문제
[ 성적이 낮은 순서로 학생 출력하기 ]
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
입력 조건
- 첫 번째 줄에 학생의 수 N이 입력된다.(1 <= N <= 100,000)
- 두 번째 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.
출력 조건
- 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.
입력 예시
2
홍길동 95
이순신 77
출력 예시
이순신 홍길동
코드
n = int(input())
arr=[]
for i in range(n):
data = input().split()
arr.append((data[0], int(data[1])))
arr = sorted(arr, key = lambda x : x[1])
for i in arr:
print(i[0], end=' ')
참조
Ch03. 정렬 알고리즘 (feat. 이것이 취업을 위한 코딩테스트다) (1)
나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리해본다. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다
jjuke-brain.tistory.com
참고 서적
이것이 취업을 위한 코딩 테스트다 with 파이썬
