내부정렬이란 정렬 중 전체데이터를 주기억 장치에 저장한 후 정렬을 수행하는 방식의 정렬입니다.
이러한 내부정렬에는 정렬방식에 따라 비교 기반 알고리즘과 데이터 분포 기반 알고리즘으로 나눌 수 있습니다.
비교 기반 알고리즘은 직접적인 데이터 비교를 통해 알고리즘을 수행하는 방식입니다.
이러한 비교 기반 알고리즘의 종류에는 선택정렬, 버블정렬, 삽입정렬, 셸정렬, 퀵정렬, 합병정렬, 힙정렬 등이 있습니다.
비교 기반의 알고리즘의 성능을 측정하는 방법은 키값의 비교횟수가 적으면 성능이 좋다고 할 수 있습니다.
비교 기반 알고리즘 중 선택정렬, 버블정렬, 삽입정렬, 셸정렬은 시간복잡도가 O(n^2)이며 퀵 정렬, 합병정렬, 힙정렬의 시간복잡도는 O(nlogn)입니다.
1. 선택정렬
선택정렬은 입력배열에서 가장 작은값부터 순서대로 선택해서 정하는 방식을 의미합니다. 즉 가장 작은 값을 찾아서 왼쪽에서 차례로 위치시키는 방식입니다. 구현방식은 첫번째 값을 찾아 그 인덱스를 최소값 인덱스로 지정한 후 모든 값을 방문하여 더 작은 값이 있다면 그 인덱스를 최소값 인덱스로 수정합니다. 그리고 정렬되지 않은 첫번째 인덱스와 최소값 인덱스의 값을 바꾸는 방식입니다.
당연히 최소값의 인덱스를 찾아야 하므로 모든 요소를 반복해야 합니다. 따라서 선택정렬은 구현은 간단하지만 효율이 매우 낮습니다.
선택정렬의 처리과정은 아래와 같습니다.
1) 순서도
2) 알고리즘
SelectionSort(A[],n)
{
for(i=0;i<n;i++){ //n-1번 반복
min = i;
for(j=i+1;j<n;j++){
if(A[j]<A[min]){
min = j;
A[i]와 A[min]의 자리바꿈
}
}
}
return A;
}
파이썬
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap with the minimum
arr[i], arr[min_index] = arr[min_index], arr[i]
data = [29, 10, 14, 37, 13]
selection_sort(data)
print("Sorted array:", data)
# Sorted array: [10, 13, 14, 29, 37]
자바
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] data = {29, 10, 14, 37, 13};
selectionSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
} // Sorted array: 10 13 14 29 37
}
}
3) 성능과 특징
위 의사코드를 보시면 이중 반복문을 사용하는 것을 볼 수 있습니다. 따라서 선택정렬의 성능은 O(n^2)이 됩니다.
또한 선택정렬의 특징으로는 입력데이터의 순서에 민감하지 않다는 것입니다. 왜냐하면 순서에 상관없이 항상 처음부터 끝까지 반복을 하게 됩니다. 따라서 입력데이터의 상태와 상관없이 항상 동일한 성능을 가지게 됩니다.
그리고 선택정렬은 제자리 정렬 알고리즘에 속합니다. 왜냐하면 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문입니다.
그리고 선택정렬은 안정적이지 않은 정렬 알고리즘에 속하게 됩니다.왜냐하면 순서대로 진행하면서 최소값과 현재의 값의 위치를 바꾸는 방식이기 때문입니다.
예컨대 입력데이터가 10,30(A),30(B),20로 주어졌을 때 선택정렬을 수행하면 30(A)와 20의 위치가 바뀌게 되어 10,20,30(B),30(A)가 됩니다.
2. 버블정렬
버블 정렬은 정렬 알고리즘에서 가장 간단하기 때문에 규현은 쉽지만 효율이 떨어지는 편입니다.
다만 기초알고리즘의 개념을 이해하는데 도움이 되기 때문에 학습은 필요합니다.
정렬 방식은 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽 데이터가 더 큰 경우에는 오른족 데이터와 자리를 바꾸는 과정을 반복해서 정렬을 수행하는 방식입니다. 여기서 비교를 진행하는 방향이 왼쪽에서 오른쪽이라면 가장 큰 값부터 찾아서 오른쪽 끝에서부터 위치 시키며, 비교를 진행하는 방향이 오른쪽에서 왼쪽으로 진행한다면 가장 작은 값부터 찾아서 왼쪽 끝에서부터 위치시킵니다.
즉 첫번째는 가장 큰 값을 마지막 자리에 위치시키며 두번째는 마지막을 제외한 자리에서 두번째로 큰 값을 위치시키면서 반복하는 것입니다.
1) 알고리즘
버블 정렬을
BubbleSort(A[],n)
{
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if(A[j]>A[j+1])
A[j]와 A[j+1]의 위치를 바꾼다.
retrun A;
}2) 성능과 특징
버블 정렬도 중첩반복문을 사용합니다. 따라서 버블정렬의 성능은 O(n^2)이 됩니다.
버블정렬은 인접한 두데이터가 동일할 경우 위치교환이 발생하지 않기 때문에 안정적이라고 할 수 있습니다. 그리고 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고도 할 수 있습니다.
버블 정렬은 선택정렬보다 데이터교환이 많이 발생합니다. 따라서 선택정렬보다 비효율적이라고 할 수 있습니다.
버블 정렬의 비효율을 개선하기 위해서 처리단계의 수를 줄이거나 인접한 두 데이터의 비교횟수를 줄임으로써 개선할 수 있습니다.
첫번째로 처리단계의 수를 줄이는 방법은 반복을 진행중에 자리바꿈이 발생하지 않으면 이미 정렬된 상태로 판단하여 이후의 처리단계를 수행하지 않고 종료하는 것입니다.
두번째로 인접한 두 데이터의 비교횟수를 줄이는 방법은 각 단계에서 왼쪽 또는 오른쪽으로 이동하면서 이미 제자리를 잡은 데이터에 대해서는 비교를 수행하지 않는 것입니다.
3) 개선된 버블정렬의 의사코드
BubbleSort(A[],n)
{
for(i=0;i<n-1;i++){
Sorted = True; //이미 정렬된 상태라고 가정
for(j=0;j<(n-1)-i;j++) //왼쪽에서 오른쪽으로 진행
if(A[j]>A[j+1]){
A[j]와 A[j+1]의 위치를 바꾼다.
Sorted = False; //자리바꿈이 발생한 것은 정렬되지 않은 상태
}
if(Soreted)) break; //자리바꿈이 발생하지 않았으므로 반복문 종료
}
retrun A;
}
파이썬
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# Swap
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print("Sorted array:", data)
# Sorted array: [11, 12, 22, 25, 34, 64, 90]
자바
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] data = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
} // Sorted array: 11 12 22 25 34 64 90
}
}
4) 개선된 버블정렬의 성능과 특징
개선된 버블정렬의 특징으로는 입력데이터의 상태에 따라 성능이 달라집니다. 위 코드를 확인해보면 정렬이 되어있는 경우 swapped가 False가 되며 그럴 경우 반복문에 break가 걸려 멈추는 것을 볼 수 있습니다. 즉 정렬이 되어있을 경우 외부 반복문은 더 이상 진행되지않기 때문에 시간복잡도가 O(n)이 되고 반대로 정렬이 역순으로 되어있다면 최악의 경우가 되어 시간복잡도는 O(n^2)이 됩니다.
3. 삽입정렬
삽입정렬은 주어진 데이터를 하나씩 뽑은 후 이미 나열된 데이터가 항상 정렬된 상태를 유지하도록 뽑은 데이터를 바른 위치에 삽입하여 정렬하는 방식입니다. 입력배열에서 정렬부분 A[0..k-1]과 미정렬부분A[k..n-1]로 구분하여 처리합니다.
처음에는 A[0]을 정렬부분으로, A[1..n-1]은 미정렬부분으로 취급한 후 시작합니다. 이때 미정렬부분A[k...n-1]에서 첫번째 데이터 A[k]를 뽑아 정렬부분 A[0..k-1]에서 제자리를 찾아서 A[k]를 삽입합니다. 그러면 정렬부분 A[0..k]가 되어 정렬상태를 유지하게 됩니다.
예를 들면 A[0] = 10, A[1] =5, A[2]= 7일 경우 처음에는 미정렬 부분은 A[1]과 A[2]가 되고 정렬부분은 A[0]가 됩니다.
이때 미정렬부분의 첫번째 데이터인 5가 정렬된 데이터 A[0]보다 작으므로 더 앞쪽에 위치시킵니다. 그러면 A[0]는 5가 되고 A[1]은 10이 됩니다. 그 다음에는 A[2]가 미정렬된 부분이 되며 A[0]와 A[1]은 정렬된 부분이 됩니다. 그리고 A[2]의 값은 7이므로 5와 10사이에 위치시킵니다. 그렇게 해서 A = [5,7,10]으로 정렬됩니다.
1) 알고리즘
InsertionSort(A[], n)
{
for (i = 1; i < n; i++){
val = A[i];
for(j=i;j>0 && A[j-1]>val;j--)
A[j] = A[j-1];
A[j] = val;
}
retrun A;
}
파이썬
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
data = [5, 3, 4, 1, 2]
insertion_sort(data)
print("Sorted array:", data)
# Sorted array: [1, 2, 3, 4, 5]
자바
public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] data = {5, 3, 4, 1, 2};
insertionSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 1 2 3 4 5
}
}2) 성능과 특징
인접한 두 데이터가 정렬되지 않은 경우에만 위치 교환이 발생하기 때문에 안정적입니다. 그리고 입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고도 할 수 있습니다.
그리고 버블정렬과 마찬가지로 입력데이터의 원래순서에 민감하여 입력데이터의 순서에 따라 성능이 달라집니다.
원하는 정렬순서의 역순으로 주어지는 경우는 최악으로써 O(n^2)이 되며 원하는 순서의 정렬상태로 주어지는 경우에는 O(n)이 됩니다. 따라서 일반적인 성능은 O(n^2)이라고 할 수 있습니다.
삽입정렬의 특징 중 하나는 탐색을 제외한 오버헤드가 매우 적으며, 배열의 크기가 작을 수록 효율적입니다.
따라서 데이터량이 작을때 고성능의 정렬 대신 사용하기도 합니다
4. 셸정렬
삽입정렬은 현재 삽입하고자 하는 데이터가 삽입될 위치에서 많이 벗어나 있어도 한번에 한자리씩만 이동해서 찾아가야 한다는 단점이 있습니다. 이러한 삽입정렬의 단점을 보완하기 위해 셸정렬이 나타났습니다.
셸정렬은 처음에는 멀리 떨어진 두 데이터를 비교하여 필요할 경우 위치를 교환하고 점점 가까운 위치의 데이터를 비교 및 교환 한 뒤 마지막에는 인접한데이터를 비교 및 교환하는 방식입니다.
이러한 방식은 입력배열을 부분 배열로 나누어 삽입정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 반복하는 것입니다.
이러한 부분배열을 나눌때 순열을 사용합니다. 순열의 역순으로 부분배열의 개수를 적용합니다.
1) 알고리즘
ShellSort(A[],n)
{
for(i=n/2;i>0;i=i/2){
for(j=i;j<n;j++){
val = A[j];
for(k=j;k>=i && A[k-i]>val;k=k-i)
A[k]=A[k-i];
A[k] = val;
}
}
retrun A;
}
2) 성능과 특징
이러한 셸정렬에서 하나의 입력배열 A[]을 물리적으로 여러개의 부분배열로 분할하는 것이 아니라 각 부분배열을 번갈아 가면서 미정렬부분의 첫번째 데이터를 뽑은 후 i만큼 떨어진 정렬부분에서 제자리를 찾아서 삽입하는 방식입니다.
또한 어떤 순열을 사용하느냐에 따라 성능이 달라집니다. 사용하는 순열에 따라 성능이 최선(O(nlogn))에서 최악(O(n^2))까지 차이가 납니다.
입력배열 A[] 이외에 상수개의 저장공간(i, min 등)만 필요하기 때문에 제자리 정렬 알고리즘이라고 할 수 있습니다. 그리고 안정적이지 않은 정렬 알고리즘입니다.
5. 퀵정렬
퀵정렬이란 특정데이터를 기준으로 주어진 배열을 2개의 부분 배열로 분할하고 각 부분배열에 대해 퀵정렬을 순환적으로 적용하는 방식입니다. 또는 피벗이 제자리를 잡은 후 분할하여 정렬하는 방식입니다.
예를 들면 요소 하나를 피벗으로 정한 후 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로 피벗보다 큰 값은 오른쪽으로 분할한 후 피벗을 가운데로 넣어줍니다. 그리고 그 다음에는 왼쪽 배열과 오른쪽 배열의 요소 하나씩을 각각 피벗으로 삼아 또 나누는 것입니다.
이것을 재귀적으로 계속 실행하여 모든 요소가 오름차순으로 정렬합니다.
피벗이란?
주어진 배열을 두 부분 배열로 분할하는 기준이 되는 특정데이터를 의미합니다. 보통 주어진 배열의 첫번째 데이터를 피벗으로 지정합니다.
1) 퀵 정렬의 알고리즘
QuickSort(A[],n)
{
if(n >1){
//피벗을 기준으로 두 부분배열로 분할
//pivot은 제자리를 잡은 피벗의 인덱스를 표시
pivot = Partition(A[0,...n-1],n);
//왼쪽 부분배열에 대한 퀵 정렬의 순환 호출
QuickSort(A[0,...pivot-1],pivot);
//오른쪽 부분배열에 대한 퀵 정렬의 순환 호출
QuickSort(A[pivot+1,...n-1],n-pivot-1);
}
}
위 알고리즘에서 분할함수 Partition함수는 아래와 같습니다.
int Partition(A[],n)
{
Left = 1;Right = n-1;
while(Left < Right){
while(Left < n && A[Left] < A[0])) Left++; //오른쪽으로 진행하면서 피벗A[0]보다 큰 값의 위치를 찾음
while(Right > 0 && A[Right] >= A[0])) Right--; //왼쪽으로 진행하면서 피벗A[0]보다 작은값의 위치를 찾음
if(Left < Right)
A[Left]와 A[Right]의 위치 교환
else
피벗 A[0]와 A[Right]의 위치 교환 // 피벗과의 위치 교환 후 while문 종료
}
retun Right;
}
파이썬
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high] # Use last element as pivot
i = low - 1 # Index of smaller element
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # Swap
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
data = [10, 7, 8, 9, 1, 5]
quick_sort(data, 0, len(data) - 1)
print("Sorted array:", data)
# Sorted array: [1, 5, 7, 8, 9, 10]
자바
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] data = {10, 7, 8, 9, 1, 5};
quickSort(data, 0, data.length - 1);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 1 5 7 8 9 10
}
}2) 성능과 특징
퀵정렬은 평균적으로 매우 빠른 정렬속도를 가지며 추가적인 메모리 사용이 적은 정렬입니다.
분할함수가 진행되면서 반복안에서 각 데이터는 피벗과 1회 또는 2회정도만 비교합니다. 따라서 분할함수의 성능은 Θ(n)이 됩니다. 즉 데이터의 개수에 비례합니다.
이때 퀵정렬의 수행시간은 분할되는 두 부분배열의 크기에 따라 달라집니다.
1] 배열이 항상 0:n-1 이나 n-1:0으로 분할되는 경우 → 최악의 경우
데이터가 오름차순이든 내림차순이든 정렬이 되어있다면 피벗은 보통 부분배열의 최소값 또는 최대값이 되는 경우가 되고 부분배열이 한쪽으로 쏠리게 되므로 최악의 경우가 됩니다.
이를 점화식으로 표현하면 다음과 같습니다. T(n) = T(n-1)+T(0)+ Θ(n)이 되며 결국 T(n) = O(n^2)이 됩니다.
2] 배열이 항상 절반으로 분할되는 경우 → 최선의 경우
이 경우는 피벗을 중심으로 항상 동일한 크기의 두 부분 배열로 분할되는 경우입니다. 즉 피벗이 항상 배열의 중간값이 되는 경우라고 할 수 있습니다.
이를 점화식으로 표현하면 다음과 같습니다. T(n) = T(n/2)+T(n/2) + Θ(n) = 2T(n/2) + Θ(n)이며 결국 T(n) = O(nlogn)이 됩니다.
이를 통해 퀵정렬의 평균 수행시간을 구해보면 T(n) = O(nlogn)이 됩니다.
그리고 퀵정렬은 제자리정렬 알고리즘이면서 안정적이지 않은 정렬 알고리즘입니다.
그런데 퀵정렬의 특징으로는 피벗선택만 제대로 한다면 평균 수행시간을 보장합니다. 즉, 피벗을 배열의 첫번째 원소로 지정하면서 배열이 정렬된 경우만 아니면 됩니다. 그런데 입력배열이 정렬되어있는지 안되어있는지는 알 수 없기 때문에 피벗을 랜덤하게 지정하면 됩니다.
일반적으로 배열의 임의의 값을 선택한 후 배열의 첫번째 원소와 교환한 후 정렬을 수행합니다.
또 다른 특징으로는 분할정복 방법이 적용된 알고리즘이기 때문에 순환 알고리즘이 되고 순환알고리즘은 점화식으로 표현할 수 있습니다.
6. 합병정렬
주어진 배열을 동일한 크기의 두 부분배열로 분할하고 각 부분배열에 순환적으로 합병정렬을 적용하여 정렬시킨 후 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 방식입니다.
1) 알고리즘
MergeSort(A[],n)
{
if(n>1){
Mid = |n /2|;
B[0,..,Mid-1] = MergerSort(A[0,..,Mid-1],Mid);
C[0,..,n-Mid-1] = MergerSort(A[Mid,..,n-1],n-Mid]);
A[0,..,n-1] = Merge(B[0,..,Mid-1],C[0,..,n-Mid-1],Mid,n-Mid);
}
return A
}
알고리즘은 2개가 남을때까지 전부 절반으로 분할합니다. 그리고 분할된 두 수를 비교한 후 정렬합니다. 그 후 역순으로 올라가면서 4,8,16... 합쳐가면서 데이터를 비교하면서 정렬합니다.
이때 합병함수 Merge()의 알고리즘은 아래와 같습니다.
Merge(B[],C[],n,m)
{
i=j=k=0;
while(i<n && j<m)
if(B[i]<=C[j])
A[k++]=B[i++];
else
A[k++]=C[j++];
for(;i<n;i++) A[k++]=B[i];
for(;j<m;j++) A[k++]=C[j];
return A[0,..,n+m-1];
}
파이썬
def merge_sort(arr, left, right):
if left >= right:
return
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
merge(arr, left, mid, right)
def merge(arr, left, mid, right):
temp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
while i <= mid:
temp.append(arr[i])
i += 1
while j <= right:
temp.append(arr[j])
j += 1
for t in range(len(temp)):
arr[left + t] = temp[t]
data = [38, 27, 43, 3, 9, 82, 10]
merge_sort(data, 0, len(data) - 1)
print("Sorted array:", data)
# Sorted array: [3, 9, 10, 27, 38, 43, 82]
자바
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int t = 0; t < temp.length; t++) {
arr[left + t] = temp[t];
}
}
public static void main(String[] args) {
int[] data = {38, 27, 43, 3, 9, 82, 10};
mergeSort(data, 0, data.length - 1);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 3 9 10 27 38 43 82
}
}
합병함수를 보면 입력배열B와 C를 비교하면서 정렬하면서 배열A에 하나씩 넣습니다.
두 입력배열 B와 C의 비교횟수는 n/2 ~ n-1번까지입니다. 따라서 합병함수의 수행시간은 Θ(n)이 됩니다.
이를 쉽게 설명하면 먼저 가까운 두개의 요소를 비교하여 정렬한 후 하나의 배열에 넣습니다. 그 다음에는 이렇게 만들어진 배열들 중 가까운 배열과 비교하여 순서대로 각 배열의 작은 값을 가져와서 정렬합니다. 이를 반복하여 모두 정렬된 최종배열이 만들어집니다.
2) 성능과 특징
이러한 합병정렬을 점화식으로 표현하면 다음과 같습니다. T(n) = T(n/2)+T(n/2) + Θ(n) = 2T(n/2) + Θ(n)이며 결국 성능은 T(n) = O(nlogn)이 됩니다.
이러한 합병정렬은 안정적인 정렬 알고리즘이지만 제자리정렬 알고리즘은 아닙니다. 왜냐하면 입력크기 n이 증가함에 따라 입력배열 B와 C의 크기도 같이 커지기되어 추가적인 공간을 요구하기 때문입니다.
또한 합병정렬도 퀵정렬과 마찬가지로 분할정복 방법이 적용된 알고리즘입니다.
7. 힙 정렬
힙 정렬은 힙이라는 자료구조의 장점을 활용한 정렬입니다.
힙(heap)이란?
각 노드의 값이 자신의 자식노드의 값보다 크거나 같은 완전 이진트리를 최대힙이라고 합니다.
각 노드의 값이 자신의 자식노드의 값보다 작거나 같은 완전 이진트리는 최소힙이라고 합니다.
일반적으로 오름차순으로 정렬할때는 최대힙을 사용하며 내림차순으로 정렬할때에는 최소힙을 사용합니다.
힙을 사용할때는 트리를 노드 순서에 따라 1차원 배열로 변환하여 사용합니다. 왜냐하면 인덱스를 조절하여 부모노드와 자식 노드를 찾을 수 있기 때문입니다.
1) 힙의 재구성 과정
힙의 첫번째 장점은 임의의 값을 삽입할 수 있습니다. 먼저 마지막 노드에 주어진 임의의 값을 넣습니다. 1차원 배열이라면 마지막에 넣는 것입니다. 이때 임의의 값이 해당 노드의 부모노드보다 크다면 자리를 교체합니다. 이것을 힙의 조건이 성립될 때까지 반복합니다.
힙의 두번째 장점은 최대값을 삭제할 수 있다는 것입니다.
최힙에서는 무조건 루트 노드가 최대값이 됩니다. 이를 삭제하기 위해서 루트노드와 마지막값을 교환합니다. 교환한 후 새로 구성된 루트노드와 자식노드보다 작다면 자식 노드 중 큰값과 교환합니다. 이것을 반복하여 힙의 조건을 성립시킵니다.
2) 힙 정렬 처리과정 순서도
3) 힙정렬 알고리즘
HeapSort(A[],n)
{
// 단계1
for(i=0;i<n;i++){
par = (i-1)/2;
while(par>=0 && A[par]<A[i]){
A[par]와 A[i] 교환;
i=par;
par = (i-1)/2;
}
}
// 단계2
for(i=n-1;i>=0;i--){
최대값A[0]와 마지막 노드 A[i]의 교환;
cur = 0; lch=1; rch=2;
do{ //힙의 재구성
if(rch <i && A[lch]<A[rch]) lch = rch;
if(A[lch] > A[cur]){
A[cur]과 A[lch]의 교환;
cur = lch;
lch = cur*2+1;
rch = cur*2+2;
}
else lch = i;
}while(lch<i)
}
return A
}
파이썬
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
# Swap
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap
heapify(arr, i, 0)
data = [12, 11, 13, 5, 6, 7]
heap_sort(data)
print("Sorted array:", data)
# Sorted array: [5, 6, 7, 11, 12, 13]
자바
public class HeapSort {
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] data = {12, 11, 13, 5, 6, 7};
heapSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 5 6 7 11 12 13
}
}
4) 힙 정렬 진행단계
힙정렬의 첫번째 단계는 주어진 1차원 배열을 힙으로 변환하는 것입니다. 이 방법에는 두가지가 있습니다.
첫번째 방법은 주어진 입력배열의 각 원소를 힙에 삽입하는 과정을 반복하는 것입니다.
예제를 통해 자세히 알아보겠습니다.
입력배열을 [60,20,70,10,80,30,50,40]이라고 가정해 보겠습니다.
1: 결과 배열의 1번째에 60을 부여합니다. → 결과 배열은 [60]이 됩니다.
2: 결과 배열의 2번째에 20을 부여합니다. 이때 20은 60보다 작기때문에 교환은 없습니다.
→ 결과 배열은 [60,20]이 됩니다.
3: 결과 배열의 3번째에 70을 부여합니다. 이때 70은 60보다 크기때문에 서로 교환합니다.
→ 결과 배열은 [70,20,60]이 됩니다.
4: 결과 배열의 4번째에 10을 부여합니다. 이때 10은 20보다 작기 때문에 교환은 없습니다.
→ 결과 배열은 [70,20,60,10]이 됩니다.
5: 결과 배열의 5번째에 80을 부여합니다. 이때 80은 20보다 크기때문에 서로 교환합니다.
→ 결과 배열은 [70,80,60,10,20]이 됩니다. 그런데 80은 70보다 크기 때문에 한번 더 교환합니다.
→ 결과 배열은 [80,70,60,10,20]이 됩니다.
6: 결과 배열의 6번째에 30을 부여합니다. 이때 30은 60보다 작기 때문에 교환은 없습니다.
→ 결과 배열은 [80,70,60,10,20,30]이 됩니다.
7: 결과 배열의 7번째에 50을 부여합니다. 이때 50은 60보다 작기 때문에 교환은 없습니다.
→ 결과 배열은 [80,70,60,10,20,30,50]이 됩니다.
8: 결과 배열의 8번째에 40을 부여합니다. 이때 40은 10보다 크기 때문에 서로 교환합니다.
→ 결과 배열은[80,70,60,40,20,30,50,10]이 됩니다.
→ 위의 결과배열은 힙이 됩니다.
두번째 방법은 주어진 입력배열을 우선 완전 이진트리로 만든 후 각 노드에 대해 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서 해당 노드의 아랫부분이 힙의 조건을 만족할 수 있도록 트리를 따라 올라가면서 자신의 자손노드들과의 위치교환을 계속해 나가는 방법입니다.
예제를 통해 자세히 알아보겠습니다.
첫번째 방법과 동일하게 입력배열이 주어졌을 때 아래 그림처럼 완전 이진트리로 만듭니다.
40→50 →30 → ...으로 진행하면서 자식노드와 값을 비교하여 힙을 만들어 나갑니다.
먼저 80까지는 자식노드가 없기때문에 확인할 값이 없습니다. 그다음부터 10과 40을 비교하여 부모노드인 10이 더 작으므로 40과 교환합니다. 20과도 비교해야겠지만 순차적으로 올라가면서 비교하기 때문에 지금은 비교하지 않습니다. 그 다음 70은 30과 50보다 크므로 변화가 없고 20에 이르렀을때 자식노드인 40,80과 비교하여 80이 더 크므로 80과 20을 교환합니다. 마지막으로 60에 이르렀을때 부모노드인 60보다 자식노드인 80이 더 크므로 또 교환합니다. 이렇게해서 힙을 구성할 수 있습니다.
힙 정렬의 두번째 단계는 최대값을 삭제하는 것입니다. (실제로 삭제하는 것은 아닙니다.)
위의 예에서 구축된 힙의 루트노드가 최대값이므로 80과 마지막 노드인 10과 교환합니다.
그 후 새로운 루트노드부터 차례로 진행하면서 힙이 재구성될수있도록 교환합니다.
새롭게 구성된 힙의 루트노드는 70이 될 것입니다. 그러면 또 70과 마지막값인 10과 교환한 후 힙을 재구성합니다.
이것을 반복하면 최종 결과는 [10,20,30,40,50,60,70,80]이 될 것입니다.
5) 성능과 특징
힙정렬은 최선, 최악, 평균수행시간은 모두 O(nlogn)이 됩니다.
왜냐하면 중첩 반복이긴 하지만, 바깥은 입력크기 n에 비례하고 안쪽은 완전이진트리의 높이 logn에 비례하기 때문에 성능은 nlogn이 됩니다.
그리고 힙정렬은 안정적이지 않은 정렬 알고리즘입니다. 그리고 제자리 정렬 알고리즘입니다.
'CS(Computer Science) 이론 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 탐색 (2) | 2024.04.27 |
|---|---|
| [알고리즘] 데이터 분포 기반 정렬 알고리즘 (2) | 2024.04.27 |
| [알고리즘] 정렬 관련 개념 (0) | 2024.04.27 |
| [알고리즘] 분석 (1) | 2024.04.27 |
| 알고리즘 개요 (2) | 2024.04.27 |