정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 학습하겠다.
1. 선택 정렬
선택 정렬(Selection Sort) 알고리즘이란 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것을 의미한다.
코드는 다음과 같다.
array = [7, 5, 1, 3, 0, 4, 2, 6, 9, 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] #swap
print(array) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]이 출력된다.
선택 정렬은 N개의 데이터가 있을 때, N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 따라서 시간 복잡도가 O(N^2)라고 표현할 수 있다. 이중반복문이기 때문이다. 따라서 데이터의 갯수가 늘어날수록 비효율적이다.
2. 삽입 정렬
삽입 정렬(Insertion Sort) 알고리즘은 특정한 데이터를 적절한 위치에 삽입하는 것을 의미한다. 삽입 정렬은 리스트의 두번째 데이터부터 시작한다. 첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다. 예를 들면 첫번째 데이터 5이고 두번째 데이터 3이라면, 3은 5보다 작으므로 5의 왼쪽으로 정렬한다. 나머지도 같은 작업을 반복한다.
코드는 다음과 같다.
array = [7, 5, 1, 3, 0, 4, 2, 6, 9, 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] #swap
else: #자기보다 작은 데이터 만나면 그 위치에서 멈춤
break
print(array) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]가 출력된다.
삽입 정렬 또한 반복문을 2번 중첩하여 사용하므로 시간 복잡도는 O(N^2)이다. 다만, 거의 정렬되어 있는 상태가 입력으로 주어진다면 매우 빠르게 동작한다.
3. 퀵 정렬
퀵 정렬(Quick Sort)은 가장 많이 사용되는 알고리즘이다. 원리는 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것이다. 퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환하기 위한 기준을 피벗이라고 한다. 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 학습하겠다.
호어 분할 방식은 리스트에서 첫번째 데이터를 피벗으로 정한다. 피벗 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
코드는 다음과 같이 재귀함수를 이용한다.
array = [7, 5, 1, 3, 0, 4, 2, 6, 9, 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)이다. 위 두 정렬 알고리즘에 비해 매우 빠른 편이다. 물론 최악의 경우 시간 복잡도가 O(N^2)가 된다. 데이터가 이미 정렬되있는 경우에는 느리게 동작한다.
4. 계수 정렬
계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
앞서 다룬 3가지 정렬 알고리즘과 달리 계수 정렬은 비교 기반 정렬 알고리즘이 아니다.
계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.
먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.
코드는 다음과 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] #리스트 선언(모든 원소의 값이 0보다 크거나 같다고 가정)
count = [0] * (max(array) + 1) #모든 범위를 포함하는 리스트 선언하고 0으로 초기화
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 = ' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력, 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9가 출력된다.
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 한다면, 계수 정렬의 시간 복잡도는 O(N + K)이다. 다만, 퀵 정렬이 일반적인 경우에 평균적으로 빠르게 동작하기에 데이터의 특성 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.
5. 정렬 라이브러리
(1) sorted()
sorted() 함수는 병합 정렬을 기반으로 만들어졌으며, 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
cf) 집합 자료형, 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.
(2) sort()
리스트를 정렬하고자 할 때는 리스트 객체의 내장함수인 sort()를 이용할 수 있다. 이를 이용하면 별도의 정렬된 리스트를 반환하지 않고 내부 원소가 바로 정렬된다.
(3) key
sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.
정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 따라서 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬 또는 퀵 정렬을 사용하자.
6. 실전 문제
(1) 위에서 아래로
Q
하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.
입력조건
첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다.
둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다.
출력조건
입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.
A
sort() 사용하여 정렬하기.
코드
n = int(input()) #정수 입력
array = list(input() for _ in range(n)) #여러 줄의 데이터를 입력받아서 리스트 선언, 문자열로 변환하기 위해 int 사용x
array.sort(reverse = True) #오름차순 정렬
print(' '.join(array)) #공백 구분하여 출력하기 위해 문자열로 변환
책에 있는 코드
n = int(input()) #정수 입력
array = list(input() for _ in range(n)) #여러 줄의 데이터를 입력받아서 리스트 선언
array.sort(reverse = True) #오름차순 정렬
for i in array:
print(i, end = ' ') #문자열로 변환하지 않고 end 사용하여 출력
(2) 성적이 낮은 순서로 학생 출력하기
Q
N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때, 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
입력조건
첫번째 줄에 학생의 수 N이 입력된다.
두번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다.
출력조건
모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력한다.
A
sorted()와 key를 이용하여 정렬한다. key = lambda를 이용하기 위해 리스트 내에 튜플로 중첩시켰다.
코드
n = int(input())
array = [0]
for i in range(n):
array[i] = list(input().split()) #2차원 리스트로 입력받기
answer = sorted(array, key = lambda x : x[1]) #리스트 내의 리스트 인덱스 1에 위치한 요소 기준으로 정렬, 즉 숫자
for i in range(n):
print(answer[i][0], end = ' ') #이름만 출력
(3) 두 배열의 원소 교체
Q
두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.
입력조건
첫번째 줄에 N, K가 공백으로 구분되어 입력된다.
두번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다.
세번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다.
출력조건
최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
A
배열 A에서 가장 작은 원소를 골라서 배열 B의 가장 큰 원소와 교체하는 것이 중요하다. 그리고 k번 반복시키는 것이 중요하다. 책의 코드와 비교해보면, 책의 코드는 sort를 반복해서 쓰지 않아서 시간복잡도 측면에서 더 효율적인 코드라고 생각한다.
코드
n, k = map(int, input().split()) #n과 k를 정수로 입력받기
array_A = list(map(int, input().split()))
array_B = list(map(int, input().split()))
for i in range(k): #k번 반복
array_A.sort() #교체한 후에 다시 오름차순으로 정렬하여 인덱스 0에 가장 작은 원소 위치시키기
array_B.sort()
if array_B[-1] > array_A[0]:
array_A[0], array_B[-1] = array_B[-1], array_A[0] #swap
print(sum(array_A))
책의 코드
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(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))
