정렬
개요
정렬이란 데이터를 특정한 기준에 따라 나열하는 것을 말한다.
만약 다음과 같은 배열이 있다고 해보자.
[3, 5, 1, 4, 0, 2]
사람의 경우엔 가장 작은 숫자를 확인한 뒤 오름차순이라면 가장 앞으로 내림차순이라면 가장 뒤로 보낼 것이다.
이러한 작업을 컴퓨터에게 시키려면 어떻게 해야할까? 여기엔 여러가지 방법이 있다. 한번 알아보자.
선택 정렬
선택 정렬이란 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸고 또 그 다음으로 작은 데이터를 선택하여 그 다음에 두는 방식으로 정렬하는 알고리즘이다.
예를 들어 위의 배열에서 가장 작은 수는 0이다.
0을 배열의 가장 앞으로 이동시키고 0번째 인덱스에 위치한 데이터인 3을 0의 자리로 보낸다.
[0, 5, 1, 4, 3, 2]
이걸 계속 반복해보자.
[0, 5, 1, 4, 3, 2]
[0, 1, 5, 4, 3, 2]
[0, 1, 2, 4, 3, 5]
[0, 1, 2, 3, 4, 5]
이런식으로 정렬시킬 수 있다.
이러한 방식을 코드로 표현해보면 다음과 같다.
array = [3, 5, 1, 4, 0, 2]
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]
선택 정렬의 시간복잡도는 중첩 반복문을 사용하여 순회하기 때문에 N^2이 된다.
삽입 정렬
다른 방법으로 정렬하는 것도 가능하다. 배열을 정방향으로 순회하며 i번째 데이터를 이미 정렬된 데이터와 비교하며 적절한 위치를 찾아 넣는 것이다.
array = [3, 5, 1, 4, 0, 2]
# 배열을 순회한다.
for i in range(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
선택 정렬과 마찬가지로 반복문이 중첩되어있기 때문에 시간복잡도는 N^2이다.
예제
` 백준 11399`
```문제 설명 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
출력 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
5
3 1 4 3 2
32
버블 정렬
버블 정렬이란 인접한 요소끼리 비교하고 swap하여 정렬하는 방식이다. 정렬 기준에 따라, 만약 오름차순 정렬을 수행한다면 큰 값이 거품처럼 배열의 끝으로 떠오른다고 해서 버블 정렬이다.
시간 복잡도는 마찬가지로 N^2가 된다.
for i in range(array - 1):
for j in range(array-1-i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
예제
백준 1377
버블 소트 알고리즘을 다음과 같이 C++로 작성했다.
bool changed = false;
for (int i=1; i<=N+1; i++) {
changed = false;
for (int j=1; j<=N-i; j++) {
if (A[j] > A[j+1]) {
changed = true;
swap(A[j], A[j+1]);
}
}
if (changed == false) {
cout << i << '\n';
break;
}
}
위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
입력
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
5
10
1
5
2
3
3
위의 코드를 보면 중첩 반복문을 돌며 만약 정렬이 일어나야한다면 change를 true로 갱신하고 변경한다. 만약 chage가 false라면, 즉 이미 정렬되어있다면 i를 출력하고 반복문을 빠져나간다.
언제 버블 정렬이 일어나지 않게 되는지 알아내는 문제다.
시간 제한은 2초로 데이터는 최대 500,000개로 4,000만번 이하의 연산 횟수로 해결해야한다. 그러나 버블 정렬은 N^2의 시간복잡도를 가지기 때문에 최악의 경우 2천 5백억의 연산횟수를 필요로한다.
따라서 시간복잡도를 최적화시킬 수 있는 아이디어를 떠올려야하는 문제다.
어떻게 할 수 있을까?
change가 false로 갱신되면 전체 반복문이 종료된다. 따라서 내부 반복문이 최종 몇 회 수행되었는가를 구하면 된다.
우선 자기 자신과 다음 데이터를 기준으로 비교와 스왑이 일어나기 때문에 데이터가 한 번에 이동할 수 있는 길이는 1이다.
그렇다면 직접 정렬하지 않고 시간복잡도가 최적화되어있는 메소드를 이용해서 정렬한 뒤 가장 많이 이동한 요소가 얼마만큼 이동했는지를 확인하면 된다.
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
A.append((int(input()), i))
Max = 0
sorted_A = sorted(A)
for i in range(N):
if Max < sorted_A[i][1] - i: # 정렬 전 index - 정렬 후 index의 최댓값 저장
Max = sorted_A[i][1] - i
print(Max + 1)
퀵 정렬
기준 데이터를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
구체적으로는 다음과 같다.
- 피벗 선택: 배열의 임의의 요소를 피벗으로 선택한다.
- 분할: 피벗을 기준으로 배열을 두 부분으로 나눈다.
- 나뉜 두 부분에 대해 다시 재귀적으로 정렬을 수행한다.
예를 들어 다음과 같은 데이터가 있다고 해보자.
[3, 6, 8, 10, 1, 2, 1]
- 임의로 요소 3을 피봇으로 선택한다.
- 3보다 큰 값과 작은 값을 나눈다.
- 배열은 [1, 2, 1], [3], [6, 8, 10]의 구조로 위치한다.
- 왼쪽에 대해 더 이상 분할할 수 없을 때까지 퀵 정렬을 시도한다.
- 오른쪽에 대해 더 이상 분할할 수 없을 때까지 퀵 정렬을 수행한다.
이렇게 이진 탐색과 마찬가지로 분할 정복 아이디어를 사용한다.
퀵 정렬의 이름에서 알 수 있듯이 퀵, 빠른 정렬이다.
최선, 평균의 경우 시간 복잡도는 NlogN이 된다.
피벗을 정하고 배열을 분할했을 때, 만약 배열이 반으로 나누어진다면 배열을 쪼개는 횟수는 logN이 되고 피벗을 기준으로 나누는 과정이 N의 시간복잡도를 가지기 때문이고 만약 피벗을 정할 때 매번 가장 큰 값이나 가장 작은 값이 선택된다면 각 단계에서 n, n-1, n-2…와 같이 비교가 발생하기 때문에 최악의 경우 시간복잡도는 N^2이 된다.
예를 들어 다음과 같은 배열이 있다고 해보자.
[1, 2, 3, 4, 5]
- 1을 피벗으로 선택한다.
- 1을 기준으로 나누면 [2, 3, 4 ,5]가 남는다.
- 다음 2를 피벗으로 선택한다면 [3, 4, 5]가 남는다.
이런 식으로 최악의 경우 배열이 반으로 나누어지지 않고 하나의 원소씩 떨어져나간다.
따라서 n + (n-1) + (n-2)…와 같은 비교 횟수가 나오고 그 값은 등차수열의 합 공식에 따라 n(n+1)/2가 된다. 상수를 무시하면 N^2이 된다.
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(rigut_side)