퀵 정렬이란?
- 일반적으로 사용되는 아주 빠른(quick) 정렬 알고리즘
- Charles A. R Hoare에 의해 고안됨
- 중심 축이 되는 값(피벗)을 선택하여 그룹을 나누어가는 방법
- 재귀적으로 호출하여 진행하는 것이 기본적인 형태
퀵 정렬은 아래와 같이 진행된다.
먼저 키가 168cm인 학생 A를 선택해서 피벗으로 삼고 이 학생을 기준으로 168cm 미만인 그룹과 168cm 이상인 그룹으로 나누고, 이 과정을 반복해서 피벗을 선택하여 나누기를 반복하여 모든 그룹이 1명씩 남으면 정렬이 완료된다.
피벗은 다른 말로 중심축이라고도 하는데, 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 상관이 없다.
배열을 두 그룹으로 나누기
1) 피벗, pl(왼쪽 커서), pr(오른쪽 커서) 선택하기
2) 그룹을 나누기 위해 피벗 이하인 원소를 배열 왼쪽(맨 앞)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤)으로 이동시키기 위해 아래 과정 수행
- a[pl] >= x가 만족하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔
- a[pr] <= x가 만족하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔
3) 스캔을 마치고 정지하는 위치에 있는 원소끼리 맞교환을 하면 피벗 이하인 원소는 왼쪽으로 이동, 피벗 이상인 원소는 오른쪽으로 이동
4) 다시 스캔을 계속하면 pl과 pr은 아래 그림의 위치처럼 정지하게 되고, arr[pl]과 arr[pr]의 값을 맞교환함.
5) 다시 스캔을 계속하게 되면 다음 그림처럼 pl과 pr이 서로 교차하게 되고, 배열은 피벗 이하인 그룹과 피벗 이상인 그룹으로 나뉜다.
- 피벗 이하인 그룹: a[0] ~ a[pl - 1]
- 피벗 이상인 그룹: a[pr + 1] ~ a[n - 1] (n은 배열의 길이)
그룹을 나누는 작업이 끝난 후 pl > pr + 1이라면, 피벗과 일치하는 그룹도 생성되는 조건임을 확인할 수 있다.
- 피벗과 일치하는 그룹: a[pr + 1] ~ a[pl - 1]
⭐️ 피벗과 일치하는 그룹일 때 같은 원소를 교환하는 작업을 하지만 이 시도는 최대 1번이므로 괜찮음.(아니면 매번 pl과 pr이 같은 위치에 있는지 확인해야 하므로 더 많은 비용이 발생하기 때문)
아래 코드는 위 과정(배열을 두 그룹으로 나누기)을 코드로 구현한 것이다.
# 배열을 두 그룹으로 나누기
from typing import MutableSequence
def partition(a: MutableSequence) -> None:
"""배열을 나누어 출력"""
n = len(a)
pl = 0 # 왼쪽 커서
pr = n - 1 # 오른쪽 커서
x = a[n // 2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr: # 배열 a를 피벗 x로 나누기
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
print(f'피벗은 {x}입니다.')
print('피벗 이하인 그룹입니다.')
print(*a[0 : pl]) # a[0] ~ a[pl - 1]
if pl > pr + 1:
print('피벗과 일치하는 그룹입니다.')
print(*a[pr + 1 : pl]) # a[pr + 1] ~ a[pl - 1]
print('피벗 이상인 그룹입니다.')
print(*a[pr + 1 : n]) # a[pr + 1] ~ a[n - 1]
if __name__ == '__main__':
print('배열을 나눕니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
partition(x) # 배열 x를 나누어서 출력
실행 결과
배열을 나눕니다.
원소 수를 입력하세요.: 9
x[0]: 1
x[1]: 8
x[2]: 7
x[3]: 4
x[4]: 5
x[5]: 2
x[6]: 6
x[7]: 3
x[8]: 9
피벗은 5입니다.
피벗 이하인 그룹입니다.
1 3 2 4 5
피벗과 일치하는 그룹입니다.
5
피벗 이상인 그룹입니다.
5 7 6 8 9
Process finished with exit code 0
⭐️ 피벗 이하, 피벗과 일치, 피벗 이상인 그룹을 출력할 때와 같이 배열의 앞에 *을 붙이면 대괄호([])를 제거해서 출력하므로 깔끔해진다.
퀵 정렬의 진행 과정
위에서 알아본 배열을 두 그룹으로 나누는 것을 조금 더 발전 시키면 퀵 정렬 알고리즘이 된다.
원소 수가 1개인 그룹은 더 이상 나눌 필요가 없기 때문에 원소 수가 2개 이상인 그룹만 다음과 같이 반복해서 나누면 된다.
- pr이 a[0]보다 오른쪽에 위치하면(left < pr) 왼쪽 그룹을 나눈다.
- pl이 a[8]보다 왼쪽에 위치하면(right > pl) 오른쪽 그룹을 나눈다.
- 가운데 그룹(a[pr + 1] ~ a[pl - 1])은 나눌 필요가 없으므로 제외한다.
다음 코드는 위에서 작성한 코드에 왼쪽 그룹과 오른쪽 그룹을 나누는 코드를 포함하여 재귀 호출로 퀵 정렬 알고리즘을 구현한 코드이다.
퀵 정렬 알고리즘 구현 코드
# 퀵 정렬 알고리즘 구현하기
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬"""
pl = left # 왼쪽 커서
pr = right # 오른쪽 커서
x = a[(left + right) // 2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr: qsort(a, left, pr)
if pl < right: qsort(a, pl, right)
def quick_sort(a: MutableSequence) -> None:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)
if __name__ == '__main__':
print('퀵 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
quick_sort(x) # 배열 x를 퀵 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
퀵 정렬을 수행합니다.
원소 수를 입력하세요.: 9
x[0]: 5
x[1]: 8
x[2]: 4
x[3]: 2
x[4]: 6
x[5]: 1
x[6]: 3
x[7]: 9
x[8]: 7
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8
x[8] = 9
Process finished with exit code 0
⭐️ 퀵 정렬은 배열을 나눌 때 피벗을 어떤 값으로 선택하느냐에 따라 성능이 달라진다.
퀵 정렬에서 나누는 과정 출력하기
# 퀵 정렬 알고리즘 구현하기(배열을 나누는 과정 출력)
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬(배열을 나누는 과정 출력)"""
pl = left # 왼쪽 커서
pr = right # 오른쪽 커서
x = a[(left + right) // 2] # 피벗(가운데 원소)
print(f'a[{left}] ~ a[{right}] : ', *a[left : right + 1]) # 새로 추가된 부분
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr: qsort(a, left, pr)
if pl < right: qsort(a, pl, right)
def quick_sort(a: MutableSequence) -> None:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)
if __name__ == '__main__':
print('퀵 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
quick_sort(x) # 배열 x를 퀵 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
퀵 정렬을 수행합니다.
원소 수를 입력하세요.: 9
x[0]: 5
x[1]: 8
x[2]: 4
x[3]: 2
x[4]: 6
x[5]: 1
x[6]: 3
x[7]: 9
x[8]: 7
a[0] ~ a[8] : 5 8 4 2 6 1 3 9 7
a[0] ~ a[4] : 5 3 4 2 1
a[0] ~ a[2] : 1 3 2
a[0] ~ a[1] : 1 2
a[3] ~ a[4] : 4 5
a[5] ~ a[8] : 6 8 9 7
a[5] ~ a[6] : 6 7
a[7] ~ a[8] : 9 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8
x[8] = 9
Process finished with exit code 0
다음 그림을 통해 배열을 나누는 과정을 한눈에 살펴볼 수 있다.
비재귀적인 퀵 정렬 만들기
# 비재귀적인 퀵 정렬 구현하기
from stack import Stack
from typing import MutableSequence
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬(비재귀적인 퀵 정렬)"""
range = Stack(right - left + 1) # 스택 생성
range.push((left, right))
while not range.is_empty():
pl, pr = left, right = range.pop() # 왼쪽, 오른쪽 커서를 꺼냄
x = a[(left + right) // 2] # 피벗(가운데 원소)
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr: range.push((left, pr)) # 왼쪽 그룹의 커서를 저장
if pl < right: range.push((pl, right)) # 오른쪽 그룹의 커서를 저장
def quick_sort(a: MutableSequence) -> None:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)
if __name__ == '__main__':
print('퀵 정렬을 수행합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
quick_sort(x) # 배열 x를 퀵 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
비재귀적으로 구현한 함수 recur( )와 마찬가지로 qsort( ) 함수에서도 데이터를 임시 저장하기 위해 다음 스택을 사용한다.
- range: 나눌 범위에서 맨 앞 원소의 인덱스와 맨 끝 원소의 인덱스를 조합한 튜플 스택
이 스택은 위 코드의 8행에서 생성된다. 스택의 크기는 right - left + 1 이며 나누는 배열의 원소 수와 같다.
위 코드에서 살펴볼 주요 부분은 다음 코드이다.
원소 수가 9이고, 원솟값이 5, 8, 4, 2, 6, 1, 3, 9, 7인 배열이 있다고 할때 아래 설명과 같이 나눌 수 있다.
10행: 튜플 (left, right)를 스택 range에 푸시한다. left와 right는 나눠야 할 배열의 범위인 맨 앞 원소 인덱스와 맨 끝 원소 인덱스이다. 이 경우 첫 번째로 튜플 (0, 8)을 푸시한다.
★ range.push((left, right))에서 바깥쪽 ( )는 함수를 호출하는 연산자이고, 안쪽 ( )는 left와 right를 튜플로 만들기 위해 식을 결합하는 연산자이다.
12행에 나오는 while 문은 스택이 비어 있지 않은 동안 작업을 반복한다.
참고로 스택은 나눠야 할 배열의 범위이므로, 스택이 비어 있다면 나눌 배열이 없다는 것이다. 반대로 스택이 비어 있지 않다면 나눠야 할 배열이 있다는 것이다.
13행: 스택에서 팝한 튜플 (pl, pr)를 (left, right)에 대입한다. 그 결과 pl과 left는 0이 되고, pr과 right는 8이 된다. 이 값은 나눠야 할 배열의 범위를 의미한다. 따라서 a[0]~a[8]을 나눈다. 그러면 a[0]~a[4]의 왼쪽 그룹과 a[5]~a[8]의 오른쪽 그룹으로 나누어진다.(pl은 5가 되고, pr는 4가 된다.)
24행: if 문에서 스택에 튜플 (0, 4)를 푸시한다.
25행: if 문에서 튜플 (5, 8)을 푸시한다. 그 결과 스택에는 (0, 4), (5, 8)이 담겨 있게 된다.
12행: while 문의 동작으로 루프 본문을 반복한다.
13행: 스택에서 팝한 튜플을 (pl, pr)와 (left, right)에 대입한다. 그 결과 pl과 left는 5가 되고, pr과 right는 8이 된다. 따라서 배열 a[5]~a[8]을 나눈다. 그러면 a[5]~a[6]의 왼쪽 그룹과 a[7]~a[8]의 오른쪽 그룹으로 나누어진다.(pl은 7이 되고, pr는 6이 된다.)
24행: if 문에서 스택에 튜플 (5, 6)을 푸시한다.
25행: if 문에서 튜플 (7, 8)을 푸시한다. 그 결과 스택에는 (0, 4), (5, 8), (7, 8)이 담겨 있게 된다.
스택에 푸시한 값은 나눠야 할 배열의 맨 앞 원소와 맨 끝 원소의 인덱스이다. 배열을 나누는 작업을 완료하면 왼쪽 그룹의 인덱스와 오른쪽 그룹의 인덱스 범위를 푸시한다. 그리고 다시 스택에서 팝한 범위를 나누는 작업을 반복하여 정렬을 수행한다. 아래 그림처럼 스택이 비면 정렬이 끝난다.
스택의 크기
위 비재귀적인 퀵 정렬 구현하기 프로그램에서 스택의 크기는 정렬 대상이 배열의 원소 수와 같은 값으로 한다. 그러면 스택의 크기는 어느 정도가 적당한지 알아보자. 아래 그림은 배열을 나누는 과정이며 이 배열을 예로 들어 살펴보자.(피벗값은 2이다.)
위 그림의 배열을 스택에 푸시하는 순서를 정할 때는 다음 2가지 규칙을 고려할 수 있다.
- 규칙 1: 원소 수가 많은 쪽의 그룹을 먼저 푸시한다.
- 규칙 2: 원소 수가 적은 쪽의 그룹을 먼저 푸시한다.
다음 두 그림을 통해 스택이 변화하는 모습을 살펴보면서 이 2가지 규칙은 어떤 차이가 있는지 자세히 알아보자.
규칙 1: 원소 수가 많은 그룹을 먼저 푸시
아래 그림의 b를 보면 a[0]~a[7]을 꺼내 a[0]~a[1]의 왼쪽 그룹과 a[2]~a[7]의 오른쪽 그룹으로 나눈다. 이때 원소 수가 많은 그룹(2, 7)을 먼저 푸시하므로 스택은 그림 c처럼 쌓인다. 그다음에는 그림 d와 같이 원소 수가 적은 그룹(0, 1)이 먼저 팝되어 나뉜다. 이렇게 하면 스택에 동시에 쌓여 있는 데이터의 개수는 그림 c, f, i와 같이 최대 2이다.
규칙 2: 원소 수가 적은 그룹을 먼저 푸시
b를 보면 a[0]~a[7]을 꺼내 a[0]~a[1]의 왼쪽 그룹과 a[2]~a[7]의 오른쪽 그룹으로 나뉜다. 원소 수가 적은 쪽인 (0, 1)을 먼저 푸시하므로 스택은 그림 c처럼 된다. 그다음에는 그림 d와 같이 원소 수가 더 많은 그룹(2, 7)이 먼저 팝되어 나뉜다. 이렇게 하면 스택에 쌓여 있는 데이터의 개수는 그림 g와 같이 최대 4이다.
일반적으로 원소 수가 적은 배열일수록 나누는 과정을 빠르게 마칠 수 있다. 따라서 앞에서 살펴본 규칙 1과 같이 원소 수가 많은 그룹의 나누기를 나중에 하고, 원소 수가 적은 그룹의 나누기를 먼저 하면 스택에 동시에 쌓이는 데이터 개수는 적어진다. 규칙 1, 2의 경우 스택에 넣고 꺼내는 횟수(푸시, 팝)는 같지만, 동시에 쌓이는 데이터의 최대 개수는 다르다.
규칙 1에서 배열의 원소 수가 n이면, 스택에 쌓이는 데이터의 최대 개수는 log n보다 적다. 따라서 원소 수 n이 100만 개라도 스택의 최대 크기는 20으로 충분하다.
피벗 선택하기
피벗 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 미친다. 다음 배열을 예로 들어보자.
피벗으로 맨 앞 원소(8)를 선택해보자. 이 배열은 피벗(8)만 있는 그룹과 나머지 원소 그룹으로 나누어야 한다.
하나의 원소와 그 외 나머지 원소로 나누는 것은 한쪽으로 완전히 치우친 분할을 반복하므로 빠른 정렬 속도를 기대할 수 없다.
빠른 정렬을 원한다면 배열을 정렬한 뒤 가운데에 위치하는 값, 즉 전체에서 중앙값을 피벗으로 하는 것이 이상적이다. 그러면 배열이 한쪽으로 치우치지 않고 절반 크기로 나누어진다. 하지만 정렬된 배열의 중앙값을 구하려면 그에 대한 처리가 필요하고, 이 처리를 위해 많은 계산 시간이 걸린다. 결국 피벗을 선택하는 의미가 없어지는 것이다.
이 문제를 해결하기 위해 다음 방법을 사용하면 최악의 경우를 피할 수 있다.
- 방법 1: 나누어야 할 배열의 원소 수가 3 이상이면, 배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택한다.
이 방법을 적용하여 위 배열에서 맨 앞 원소(8), 가운데 원소(4), 맨 끝 원소(0) 중에서 중앙값인 4를 피벗으로 선택하면 치우치지 않고 나눌 수 있다.
방법 1을 한 단계 더 발전시키면 다음과 같이 방법 2가 나온다.
- 방법 2: 나누어야 할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두 번째 원소를 교환한다. 맨 끝에서 두 번째 원솟값 a[right - 1]이 피벗으로 선택되었고, 그 동시에 나눌 대상을 a[left + 1] ~ a[right - 2]로 좁힌다.
이제 방법 2를 적용하여 아래 내용을 구체적으로 살펴보자.
a: 정렬하기 전의 상태이다. 맨 앞 원소(8), 가운데 원소(4), 맨 끝 원소(0)를 정렬한다.
b: 정렬한 후 맨 앞 원소는 0, 가운데 원소는 4, 맨 끝 원소는 8이 된다. 여기서 가운데 원소(4)와 맨 끝에서 두 번째 원소(1)를 교환한다.
c: 이때 맨 끝에서 두 번째 원소에 위치한 값(4)을 피벗으로 선택한다. a[left]의 0은 피벗 이하인 값이고, a[right - 1]과 a[right]의 4와 8은 피벗 이상인 값이다.
이 과정을 거치고 나면 스캔할 커서의 시작 위치(pl, pr)를 다음과 같이 변경하여 나눌 대상 범위를 좁힐 수 있다.
- 왼쪽 커서 pl의 시작 위치: left → left + 1(오른쪽으로 1칸 옮김)
- 오른쪽 커서 pr의 시작 위치: right → right - 2(왼쪽으로 2칸 옮김)
이 방법을 사용하면 나누는 그룹이 한쪽으로 치우치는 것을 피할 수 있고, 스캔할 원소를 3개 줄일 수 있다. 그 결과 이 방법을 사용하지 않을 때보다 조금 더 빠른 속도로 정렬할 수 있다.
퀵 정렬의 시간 복잡도
퀵 정렬은 배열을 조금씩 나누어 보다 작은 문제를 푸는 과정을 반복하므로 시간 복잡도는 O(n log n)이다. 그런데 정렬하는 배열의 초깃값이나 피벗을 선택하는 방법에 따라 실행 시간 복잡도가 증가하는 경우도 있다. 예를 들어 매번 1개의 원소와 나머지 원소로 나누어진다면 n번의 분할이 필요하다. 이러한 최악의 경우 시간 복잡도는 O(n^2)이 된다.
퀵 정렬은 원소 수가 적은 경우에는 그다지 빠른 알고리즘이 아닌 것으로 알려져 있다.
아래는 다음 2가지 방법을 적용하여 원소 수가 9개 미만이면 단순 삽입 정렬로 전환하도록 만든 프로그램이다.
- 원소 수가 9개 미만인 경우 단순 삽입 정렬로 전환한다.
- 피벗 선택은 방법 2를 채택한다.
# 퀵 정렬 알고리즘 구현하기(원소 수가 9 미만이면 단순 삽입 정렬)
from typing import MutableSequence
def sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int):
"""a[idx1], a[idx2], a[idx3]을 오름차순으로 정렬하고 중앙값의 인덱스를 반환"""
if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
if a[idx3] < a[idx2]: a[idx3], a[idx2] = a[idx2], a[idx3]
if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
return idx2
def insertion_sort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 단순 삽입 정렬"""
for i in range(left + 1, right + 1):
j = i
tmp = a[i]
while j > 0 and a[j - 1] > tmp:
a[j] = a[j - 1]
j -= 1
a[j] = tmp
def qsort(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 퀵 정렬"""
if right - left < 9: # 원소 수가 9 미만이면 단순 삽입 정렬로 전환
insertion_sort(a, left, right)
else:
pl = left # 왼쪽 커서
pr = right # 오른쪽 커서
m = sort3(a, pl, (pl + pr) // 2, pr)
x = a[m]
a[m], a[pr - 1] = a[pr - 1], a[m]
pl += 1
pr -= 2
while pl <= pr:
while a[pl] < x: pl += 1
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl],
pl += 1
pr -= 1
if left < pr: qsort(a, left, pr)
if pl < right: qsort(a, pl, right)
def quick_sort(a: MutableSequence) -> None:
"""퀵 정렬"""
qsort(a, 0, len(a) - 1)
if __name__ == '__main__':
print('퀵 정렬을 합니다(원소 수가 9 미만이면 단순 삽입 정렬을 합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
quick_sort(x) # 배열 x를 퀵 정렬
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
퀵 정렬을 합니다(원소 수가 9 미만이면 단순 삽입 정렬을 합니다.)
원소 수를 입력하세요.: 12
x[0]: 5
x[1]: 8
x[2]: 4
x[3]: 2
x[4]: 6
x[5]: 1
x[6]: 3
x[7]: 9
x[8]: 7
x[9]: 0
x[10]: 3
x[11]: 5
오름차순으로 정렬했습니다.
x[0] = 0
x[1] = 1
x[2] = 2
x[3] = 3
x[4] = 3
x[5] = 4
x[6] = 5
x[7] = 5
x[8] = 6
x[9] = 7
x[10] = 8
x[11] = 9
Process finished with exit code 0
sorted( ) 함수로 정렬하기
파이썬에서는 정렬을 수행하는 sorted( ) 함수를 내장 함수로 제공한다.
이 함수는 전달받은(임의의 자료형) 이터러블 객체의 원소를 정렬하여 list형으로 반환한다.
sorted( ) 함수는 '정렬을 직접 수행'하지 않고 '정렬을 수행한 뒤 늘어선 원소를 새로운 리스트로 생성하여 반환'한다.
이 함수는 다음과 같이 간단하게 사용할 수 있다.
a, b = sorted([a, b]) # a, b를 오름차순으로 정렬
a, b, c = sorted([a, b, c]) # a, b, c를 오름차순으로 정렬
a, b, c, d = sorted([a, b, c, d]) # a, b, c, d를 오름차순으로 정렬
이 3가지 예시에서는 변수(a, b, ...)를 나열한 리스트를 sorted( ) 함수에 전달하고, 반환된 리스트를 풀어 변수(a, b, ..)에 대입한다. sorted( ) 함수는 오름차순을 기본으로 하지만, reverse에 True 값을 넘겨주면 내림차순 정렬을 수행한다.
아래 프로그램은 sorted( ) 함수를 사용하여 리스트를 정렬하는 프로그램으로 오름차순 정렬과 내림차순 정렬을 모두 수행한다.
# sorted( ) 함수를 사용하여 정렬하기
print('sorted( ) 함수를 사용하여 정렬합니다.')
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
# 배열 x를 오름차순 정렬
x = sorted(x)
print('오름차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
# 배열 x를 내림차순으로 정렬
x = sorted(x, reverse = True)
print('내림차순으로 정렬했습니다.')
for i in range(num):
print(f'x[{i}] = {x[i]}')
실행 결과
sorted( ) 함수를 사용하여 정렬합니다.
원소 수를 입력하세요.: 5
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
내림차순으로 정렬했습니다.
x[0] = 7
x[1] = 6
x[2] = 4
x[3] = 3
x[4] = 1
Process finished with exit code 0
튜플은 이뮤터블의 속성을 가지므로 튜플 자체를 정렬할 수는 없다. 튜플을 정렬해야 한다면 다음과 같은 2단계 방법을 사용한다.
- 1단계: sorted( ) 함수로 정렬한 원소의 나열에서 새로운 리스트를 생성한다.
- 2단계: 생성한 리스트를 튜플로 변환한다.
아래는 프롬프트를 통해 튜플을 정렬하는 과정이다.
>>> x = (1, 3, 2)
>>> x = tuple(sorted(x))
>>> x
(1, 2, 3)
'자료구조, 알고리즘 입문 > 정렬 알고리즘' 카테고리의 다른 글
| [정렬 알고리즘] 병합 정렬(합병 정렬, 머지 소트, 머지 정렬) (1) | 2024.09.24 |
|---|---|
| [정렬 알고리즘] 퀵 정렬 - 피벗을 선택하는 두 가지 방법 (0) | 2024.09.22 |
| [정렬 알고리즘] 단순 삽입 정렬(셔틀 정렬), 이진 삽입 정렬 (0) | 2022.05.26 |
| [알고리즘] 단순 선택 정렬 (0) | 2022.05.23 |
| [알고리즘] 셰이커 정렬, 파이썬 내장 함수 (0) | 2022.05.19 |