정렬이란?
데이터들을 작은 순 또는 큰 순(특정한 규칙)으로 정렬하는 것이며,
주어진 숫자를 순서대로 나열하는 것
정렬은 흔히 볼 수있는 이메일이나 수험생 시험성적 등 다양한 곳에 사용된다.
데이터를 작은 순서대로 정렬하면 '오름차순', 큰 순서대로 정렬하면 '내림차순'이라고 한다.
정렬은 왜 하는 것일까?
- 이분탐색을 이용하려면 집합의 원소들이 정렬되어 있어야 한다.
- 문제를 해결함에 있어 결과적으로 효율적인 연산횟수를 내기 위해서이다.
정렬은 기본이 되는 작업으로, 다양한 알고리즘이 고안되어 있다.
버블 정렬(bubble sort)
오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복한다.
숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 한다.
- 수열의 오른쪽 끝에 있는 두 값을 비교하여 오른쪽 숫자가 작으면 왼쪽 숫자와 교체한다.
- 한 칸 이동 후 다시 두 값을 비교한 후 위와 같은 방법으로 정렬한다.
- 왼쪽 끝에 있는 값까지 (1)~(2)작업을 반복하면, (1라운드)수열 중에서 가장 작은 값이 왼쪽 끝으로 오게 된다.
- 왼쪽 끝 첫번째 값은 정렬을 끝낸 것으로 간주하여 제외하고, 나머지 수열들을 다시 (1)~(3)작업을 반복한다.
버블 정렬은 1라운드에서 n-1회, 2라운드에서 n-2회, ... n라운드에서 1회를 비교한다.
이 때문에 비교 횟수는 (n-1)+(n-2)+ … + 2 + 1 = n(n-1)/2 이다.
이 비교 횟수는 입력 데이터의 순서와 상관없이 일정하고, 숫자의 교체 횟수는 입력 데이터에 의존한다.
극단적으로 입력 데이터가 우연히 작은 순서대로 나열돼 있을 때는 교체가 한 번도 발생하지 않고,
반대로 숫자가 큰 순서대로 나열돼 있으면 비교할 때마다 교체해 주어야 한다.
따라서 시간복잡도는 O(n)가 된다.
소스코드
python
def bubbleSort(x):
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return xJava
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j]<arr[j-1]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}정리
버블정렬 : 인접한 두 개의 숫자를 비교해서 교환하는 정렬 방법
- 장점
- 구현이 매우 간단하다.
- 단점
- 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 한다.
- 특히 특정 요소가 이미 최종 정렬 위치에 있는 경우라도 교환이 일어난다.
- T(n) = O(n)
선택 정렬(selection sort)
수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다.
수열 중에서 최솟값을 찾을 때는 선형 탐색을 사용한다.
선형탐색?
배열에서 앞에서부터 순서대로 데이터를 탐색하는 알고리즘.
이진 탐색과 달리 데이터가 질서정연하게 나열되어 있지 않아도 적용할 수 있다.
- T(n) = O(n)
- 수열을 선형 탐색해서 최솟값을 찾는다.
- 최솟값을 왼쪽 끝에 있는 수와 교체한 뒤 정렬이 끝난 것으로 간주한다.
- 모든 값이 정렬될 때까지 (1)~(2) 작업을 반복한다.
선택 정렬은 1라운드에서 n-1회, 2라운드에서 n-2회, ... n라운드에서 1회를 비교한다.
이 때문에 비교 횟수는 (n-1)+(n-2)+ … + 2 + 1 = n(n-1)/2 이다. - 버블정렬과 같다
또한, 숫자 교체는 각 라운드에서 최대 1회이다. 입력 데이터가 작은 순으로 나열돼 있다면 교체는 한 번도 발생하지 않는다. 따라서 시간복잡도는 O(n)가 된다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
선택 정렬에서는최대 n개의 교환 작업이 필요하지만, 버블 정렬에서는 각 요소에 대해 최대 n개의 교환 작업이 발생하므로 최대 n개의 교환 작업이 필요하다.
이러한 교환 작업은 메모리를 많이 사용하므로 큰 배열의 경우 선택 정렬이 버블 정렬보다 훨씬 더 효율적이다.
선택 정렬은 일반적으로 메모리 쓰기 가 메모리 읽기보다 비용이 많이 드는 경우에 사용
소스코드
python
def selectionSort(x):
length = len(x)
for i in range(length-1):
indexMin = i
for j in range(i+1, length):
if x[indexMin] > x[j]:
indexMin = j
x[i], x[indexMin] = x[indexMin], x[i]
return xJava
void selectionSort(int[] list) {
int indexMin, temp;
for (int i = 0; i < list.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[indexMin]) {
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}정리
선택 정렬 : 수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 정렬 방법
- 장점
- 추가 메모리가 필요없다.
- 자료 이동 횟수가 미리 결정된다.
- 시간 복잡도 O(n)인 정렬 알고리즘에서 버블 정렬보다 우수하다.
- 단점
- 동일한 값이 있는 경우에 상대적인 위치가 변경될 수 있다.
- 개선 방법
- 이중 선택 정렬 : 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다.
- 탐색을 응용하여 개선 : 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법이다. 같은 값이 많을 수록 유용하다.
- T(n) = O(n)
삽입 정렬(insertion sort)
수열의 왼쪽부터 순서대로 정렬하는 방식이다.
미탐색 영역에서 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나간다.
- 처음에는 왼쪽 끝의 수를 정렬이 끝난 상태로 간주한다.
- 미탐색 영역의 왼쪽 끝에 있는 수를 정렬이 끝난 영역의 수와 비교하며 위치를 교체한다.
- 같은 방식으로 미탐색 영역의 모든 값이 정렬될 때까지 (1)~(2)를 반복한다.
삽입 정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교하는데, 만약 왼쪽에 있는 숫자가 작다면 교체가 발생하지 않는다.
미탐색 영역에서 정렬할 대상 숫자가 정렬이 끝난 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체작업을 하게 된다.
구체적으로 k운드에서는 k-1회씩 작업을 하는데, 최악의 경우에는 2라운드에서 1회, 3라운드에서 2회, ..., n라운드에서 n-1회의 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택 정렬과 같이 O(n)가 된다.
소스코드
python
def insert_sort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j]
j = j - 1
x[j+1] = key
return xJava
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){
int temp = arr[index];
int aux = index - 1;
while( (aux >= 0) && ( arr[aux] > temp ) ) {
arr[aux + 1] = arr[aux];
aux--;
}
arr[aux + 1] = temp;
}
}정리
삽입 정렬 : 미탐색 영역에서 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해나가며 정렬하는 방법
- 장점
- 추가 메모리가 필요없다.
- 구현이 간단하다.
- 같은 값의 원소 순서를 유지한다.(안정 정렬)
- 값이 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
- 단점
- 배열이 길어질수록 효율이 떨어진다.
- Best T(n) = O(n)
- Worst T(n) = O(n)
힙 정렬(heap sort)
힙(heap) 데이터 구조를 사용하는 정렬 방법이다.
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는데,
내림차순 정렬을 위해서 최소 힙을 구성하고, 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.
- 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) >= key(자식 노드)
- 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) <= key(자식 노드)
힙(heap)?
그래프의 트리 구조 중 하나로, '우선순위 큐(priority queue)'를 구현할 때 사용된다.
우선순위 큐는 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있다.
반면, 데이터를 추출할 때는 최솟값부터 순서대로 선택된다.
추가는 자유롭게 하고 추출할 때는 작은 값부터 꺼내는 것이 우선순위 큐이다.
또한, 힙을 표현하는 트리 구조에서는 각 정점을 '노드(node)'라고 부른다.
힙에서는 각 노드에 데이터가 저장된다.
힙의 각 노드에 적혀 있는 숫자는 저장돼 있는 데이터이다.
이 노드들은 최대 두 개의 자식 노드를 가진다.
또한, 트리의 모양은 데이터의 개수에 의해 정해진다.
노드는 위에서부터 채워지며, 같은 층(단)에서는 왼쪽부터 채워진다.
- n개의 노드에 완전 이진 트리를 구성
- 내림차순 정렬을 위해서는 최대 힙 구성/오름차순 정렬을 위해서는 최소 힙 구성
- 가장 위에 있는 요소를 추출하여 배열에 저장(최소 힙이면 최솟값, 최대 힙이면 최댓값)
- 최대 힙은 꺼낸 요소를 역순으로 나열하면 정렬이 된다.
- 다시 힙을 재구축하여 같은 방식으로 루트 노드에 있는 요소를 추출하여 배열에 저장하기를 반복
- 모든 요소들을 힙에서 꺼내면 정렬이 완료된다.
힙(heap) 삽입
- 힙에 새로운 요소가 들어오면, 힙의 마지막 노드에 삽입한다.
- 새로운 노드를 부모 노드와 교환하며 힙의 성질을 만족시킨다.
힙(heap) 삭제
- 최댓값, 최솟값을 지닌 루트 노드를 추출(삭제)하게 되면 힙의 구조를 다시 정리해야 한다.
- 삭제된 루트 노드에는 힙의 마지막 노드를 가장 위로 이동시킨다.
- 자식 노드들과 비교하며 힙의 성질을 만족하는 노드들과 교환한다.
- 교환이 발생하지 않을 때까지 반복한다.
정리
힙 정렬 : 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
- 장점
- 시간 복잡도가 좋은 편이다.
- 최댓값이나 최솟값을 자주 추출해야 하는 경우네는 힙 정렬이 편리하다.
- 예를 들어, 다익스트라 알고리즘에서 후보가 되는 노드 중에서 최솟값을 매 단계에서 선택하는데, 이때 노드를 관리하기 위해 힙을 사용하는 경우도 있다.
- T(n) = O(n log n)
힙의 높이가 logn 이하이므로 1회 추가에 O(log n)의 시간이 걸리고 각 라운드에서 최대 숫자를 꺼내서 힙을 재구축하는 데 걸리는 시간은 O(log n)이다. 라운드 수는 n이므로 힙이 완성된 후에 정렬하는 시간도 O(n log n)이 된다. 따라서 힙 정렬의 계산 시간은 전체적으로 O(n log n)이 된다.
소스코드
python
def heapify(li, idx, n):
l = idx * 2
r = idx * 2 + 1
s_idx = idx
if (l <= n and li[s_idx] > li[l]):
s_idx = l
if (r <= n and li[s_idx] > li[r]):
s_idx = r
if s_idx != idx:
li[idx], li[s_idx] = li[s_idx], li[idx]
return heapify(li, s_idx, n)
def heap_sort(v):
n = len(v)
v = [0]+v
# main heap 생성
for i in range(n, 0, -1):
heapify(v, i, n)
# min element extract & heap
for i in range(n, 0, -1):
print(v[1])
v[i], v[1] = v[1], v[i]
heapify(v, 1, i-1)
heap_sort([5,3,4,2,1]) Java
public class Heap
{
private int[] element; //element[0] contains length
private static final int ROOTLOC = 1;
private static final int DEFAULT = 10;
public Heap(int size) {
if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
else {element = new int[DEFAULT+1]; element[0] = 0;}
}
public void add(int newnum) {
if(element.length <= element[0] + 1) {
int[] elementTemp = new int[element[0]*2];
for(int x = 0; x < element[0]; x++) {
elementTemp[x] = element[x];
}
element = elementTemp;
}
element[++element[0]] = newnum;
upheap();
}
public int extractRoot() {
int extracted = element[1];
element[1] = element[element[0]--];
downheap();
return extracted;
}
public void upheap() {
int locmark = element[0];
while(locmark >= 1 && element[locmark/2] > element[locmark]) {
swap(locmark/2, locmark);
locmark /= 2;
}
}
public void downheap() {
int locmark = 1;
while(locmark * 2 <= element[0])
{
if(locmark * 2 + 1 <= element[0]) {
int small = smaller(locmark*2, locmark*2+1);
swap(locmark,small);
locmark = small;
}
else {
swap(locmark, locmark * 2);
locmark *= 2;
}
}
}
public void swap(int a, int b) {
int temp = element[a];
element[a] = element[b];
element[b] = temp;
}
public int smaller(int a, int b) {
return element[a] < element[b] ? a : b;
}
}병합 정렬(merge sort)
정렬하고 싶은 리스트을 두 개의 리스트로 분할하여 더 이상 분할되지 않는 상태에 이르면 그룹들을 병합한다.
병합할 때에는 정렬이 끝난 두 개의 리스트를 병합해서 정렬이 끝난 하나의 리스트로 만든다.
이것을 전체가 하나의 그룹이 될 때까지 반복하는 정렬 방법이다.
- 분할(divide) : 정렬되지 않은 리스트를 절반으로 나눈다.
- 정복(conquer) : 각 부분 리스트를 재귀적으로 병합 정렬을 한다.
- 여러 값을 포함하고 있는 리스트들을 서로 병합할 때는 선두의 값을 비교해서 작은 값을 이동시킨다.
- 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 이때 정렬 결과가 임시 배열에 저장된다.
- 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
정리
병합 정렬 : 분할 및 정복 알고리즘이다.
리스트를 분할해 갈 때는 계산 시간이 걸리지 않는다.
두 개의 정렬이 끝난 리스트를 병합하는 부분은 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 리스트의 길이에 따라 달라진다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 요소들의 수가 된다.
- T(n) = O(n log n)
- 장점
- 안정적인 정렬 방법이다.
- 최악의 경우 런타임이 O(nlogn)이므로 더 효율적이다.
- 단점
- 많은 공간(O(n))이 필요하므로 경우에 따라 마지막 데이터에 대한 작업이느려질 수 있다.
Java 및 기타 많은 언어는 객체 정렬을 위한 기본 기술로 병합 정렬을 사용한다고 한다.
소스코드
python
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
low_arr = merge_sort(arr[:mid])
high_arr = merge_sort(arr[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
return merged_arrJava
public class MergeSorter {
public static int[] sort(int[] arr) {
if (arr.length < 2) return arr;
int mid = arr.length / 2;
int[] low_arr = sort(Arrays.copyOfRange(arr, 0, mid));
int[] high_arr = sort(Arrays.copyOfRange(arr, mid, arr.length));
int[] mergedArr = new int[arr.length];
int m = 0, l = 0, h = 0;
while (l < low_arr.length && h < high_arr.length) {
if (low_arr[l] < high_arr[h])
mergedArr[m++] = low_arr[l++];
else
mergedArr[m++] = high_arr[h++];
}
while (l < low_arr.length) {
mergedArr[m++] = low_arr[l++];
}
while (h < high_arr.length) {
mergedArr[m++] = high_arr[h++];
}
return mergedArr;
}
}퀵 정렬(quick sort)
기준이 되는 수(피봇(pivot))를 수열 안에서 임의로 하나를 선택하여 피봇 이외의 수를 '피봇보다 작은 수'와 '피봇 이상인 수'의 두 그룹으로 나누고 "피봇보다 작은 수 < 피봇 < 피봇 이상인 수"로 배치한다.
퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
- 리스트 가운데 임의로 기준이 되는 수(피봇)을 선택한다.
- 피봇 앞에는 피봇보다 작은 값을, 뒤에는 피봇보다 큰 값을 이동시킨다.
- 피봇 기준으로 왼쪽과 오른쪽 두 리스트도 각각 위 (1)~(2) 과정을 재귀적으로 반복한다.
- 각 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복
단계
- 분할(divide) : 배열을 피봇 기준으로 비균등하게 2개의 부분 배열로 분할
- 정복(conquer) : 부분 배열을 정렬하여 부분 배열의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할 정복 방법 적용
- 결합(combine) : 정렬된 부분 배열들을 하나의 배열에 합병
정리
퀵 정렬 : 분할 정복 방법을 통해 정렬하는 방법이다.
리스트를 분할해 갈 때는 계산 시간이 걸리지 않는다.
두 개의 정렬이 끝난 리스트를 병합하는 부분은 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 리스트의 길이에 따라 달라진다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 요소들의 수가 된다.
- T(n) = O(n log n)
배열들을 반으로 분할하는 과정을 logn회 반복하면 요소가 하나의 배열이 되어 정렬이 완료가 된다.
각 층에서 각 요소는 피봇과 1회만 비교되므로 한 층의 계산 시간은 O(n)이 되어 전체 계산 시간은 O(n log n)이 된다.
최악의 경우 최솟값이 피봇으로 선택되면 모든 숫자가 피봇보다 오른쪽으로 가기 때문에(불균형하게 분할) 재귀가 n층이 돼서 계산 시간이 O(n)가 된다.
균형있게 분할할 수 있는 피봇을 선택하면 평균적으로 O(n log n)의 계산 시간이 걸린다.
시간 복잡도가 O(n log n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결저오딘 피봇들이 추후 연산에서 제외되는 특성 때문이다.
- 장점
- 속도가 빠르다
- 시간 복잡도가 O(n log n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
- 추가 메모리 공간을 필요로 하지 않는다.
- O(log n)만큼의 메모리 필요
- 단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
불균형 분할을 방지하기 위하여 피봇을 선택할 때 리스트를 균등하게 분할할 수 있는 데이터(ex, 중앙값)를 선택한다.
소스코드
python
def quicksort(x):
if len(x) <= 1:
return x
pivot = x[len(x) // 2]
less = []
more = []
equal = []
for a in x:
if a < pivot:
less.append(a)
elif a > pivot:
more.append(a)
else:
equal.append(a)
return quicksort(less) + equal + quicksort(more)Java
public void quickSort(int[] arr, int left, int right) {
int i, j, pivot, tmp;
if (left < right) {
i = left; j = right;
pivot = arr[(left+right)/2];
//분할 과정
while (i < j) {
while (arr[j] > pivot) j--;
// 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
while (i < j && arr[i] < pivot) i++;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//정렬 과정
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
}Reference
