Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 을 개인적으로 정리하는 글임을 알립니다.
정렬
정렬은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다.
정렬 알고리즘의 안정성 동일한 키 값을 가진 요소들의 상대적인 순서가 정렬 전과 정렬 후에도 유지되는 정렬 특성을 나타낸다. 안정적인 정렬 알고리즘은 동일한 키 값을 가진 요소들 간의 순서를 보존하는 특성을 갖는다. 위 그림의 왼쪽과 같이 학번, 점수가 학번 순으로 나열되어있다. 이때 점수를 기준으로 오름차순 정렬을 하면 오른쪽 그림과 같다. 점수가 같을 때는 학번이 작은 사람을 앞쪽에 배치한다. 안정된 정렬이란 이렇게 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 점수가 같을 때 반드시 학번 순서대로 정렬되지는 않는다.
안정적인 정렬 알고리즘의 예로는 버블 정렬, 삽입 정렬, 병합 정렬이 있다. 반면에 선택 정렬과 퀵 정렬은 일반적으로 안정적이지 않는다.
내부 정렬과 외부 정렬 하나의 배열에서 작업할 수 있을 때에는 내부정렬을 사용하고, 하나의 배열에서 작업할 수 없을 때에는 외부 정렬을 사용한다.
-내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘 -외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘
버블 정렬(Bubble Sort)
버블 정렬(Bubble Sort)은 간단하지만 비효율적인 정렬 알고리즘 중 하나이다.
이 알고리즘은 인접한 두 요소를 비교하여 순서가 맞지 않은 경우에 교환하는 방식으로 동작한다.
이 과정을 배열의 끝까지 반복하면서 정렬을 수행한다.
알고리즘의 이름은 정렬 과정에서 작은 요소가 배열의 뒤로 "거품처럼" 올라가는 듯한 모습에서 유래되었다.
버블 정렬의 기본 아이디어는 다음과 같다.
배열의 첫 번째 요소부터 마지막 요소까지 반복
현재 요소와 다음 요소를 비교하여 순서가 맞지 않으면 두 요소를 교환
배열의 끝까지 도달할 때까지 1과 2의 과정을 반복
1회전이 끝나면 가장 큰 요소가 배열의 마지막 자리로 이동
배열의 마지막 요소는 정렬이 완료된 것으로 간주하고, 다시 처음부터 반복
정렬이 완료될 때까지 반복
https://javaplant.tistory.com/16
이 알고리즘의 시간 복잡도는 최악과 평균 모두 O(n^2)이다.
최선의 경우에도 O(n)의 시간이 걸릴 수 있다.
따라서 대부분의 실제 상황에서는 효율적인 정렬 알고리즘들이 사용되는 편이다.
버블 알고리즘은 안정된 정렬 알고리즘이다.
public class Main {
static void bubbleSort(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
for (int j = 0; j < arr.length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
// 두 요소 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
public static void main(String[] args) {
int[] myArray = {64, 34, 25, 12, 22, 11, 90};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 버블 정렬 수행
bubbleSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
}
단순 선택 정렬(Simple Selection Sort)
단순 선택 정렬(Simple Selection Sort)은 배열을 정렬하는 간단하면서도 비효율적인 정렬 알고리즘 중 하나이다.
이 알고리즘은 선택 정렬(Selection Sort)의 한 형태로, 배열에서 가장 작은 원소를 찾아 첫 번째 위치에 배치한 후, 그 다음으로 작은 원소를 찾아 두 번째 위치에 배치하는 과정을 반복하여 정렬을 수행한다.
단순 선택 정렬의 기본 아이디어는 다음과 같다.
배열의 처음부터 끝까지를 반복하면서 최소값을 찾는다.
최소값을 현재 검사 중인 요소와 교환.
다음 위치로 이동하여 나머지 부분에 대해서 위의 과정을 반복.
이 과정을 전체 배열에 대해 반복하면서 정렬을 완료.
단순 선택 정렬의 시간 복잡도는 항상 O(n^2)이다.
알고리즘은 비교 연산을 통해 최소값을 찾고, 교환을 통해 정렬을 진행하므로 비효율적인 정렬 방법 중 하나이다.
단순 선택 정렬은 일반적으로 안정적인 정렬 알고리즘은 아니다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 단순 선택 정렬 수행
selectionSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void selectionSort(int[] arr)
{
for (int i = 0; i < arr.length - 1; i++)
{
// 최소값의 인덱스를 찾기
int minIndex = i;
for (int j = i+1; j < arr.length; j++)
{
if (arr[j] < arr[minIndex]) minIndex = j;
}
// 최소값과 현재 요소 교환
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
단순 삽입 정렬(Simple Insertion Sort)
단순 삽입 정렬(Simple Insertion Sort)은 배열을 정렬하는 간단하면서도 효율적인 정렬 알고리즘 중 하나이다.
이 알고리즘은 현재 위치에서 그보다 앞에 있는 원소들과 비교하여 자신이 들어갈 위치를 찾아 삽입하는 방식으로 동작한다.
배열의 각 요소를 이미 정렬된 부분과 비교하면서 적절한 위치에 삽입하면서 전체 배열을 정렬한다.
단순 삽입 정렬의 기본 아이디어는 다음과 같다.
배열의 두 번째 요소부터 시작하여 현재 위치에서 그보다 앞에 있는 원소들과 비교.
현재 위치의 원소가 더 작은 원소를 만날 때까지 계속하여 비교하며, 자신이 들어갈 위치를 찾는다.
찾은 적절한 위치에 현재 위치의 원소를 삽입.
배열의 모든 요소에 대해 위의 과정을 반복하여 정렬을 완료.
단순 삽입 정렬의 시간 복잡도는 최선의 경우에는 O(n), 평균 및 최악의 경우에는 O(n^2)이다.
이는 배열이 이미 정렬되어 있는 경우에는 삽입 과정이 매우 효율적으로 이뤄지기 때문이다.
단순 삽입 정렬은 안정적인 정렬 알고리즘이다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 단순 삽입 정렬 수행
insertionSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void insertionSort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int key = arr[i];
int j = i - 1;
// key보다 큰 원소들을 오른쪽으로 이동
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
// key를 적절한 위치에 삽입
arr[j + 1] = key;
}
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
셸 정렬(Shell Sort)
셸 정렬(Shell Sort)은 단순 삽입 정렬의 장점을 살리고 단점을 보완하여 좀 더 빠르게 정렬하는 알고리즘이다.
단순 삽입 정렬의 장점과 단점 아래의 배열에서 단순 삽입 정렬을 수행한다고 가정해보자. 2, 3, 4, 5 순서로 선택하여 정렬한다. 여기까지는 이미 정렬이 되어 있는 상태이기 때문에 요소를 이동(값의 대입)하지 않는다. 그러므로 5까지는 빨리 정렬할 수 있다. 그러나 0을 삽입하려면, 아래와 같이 총 6회에 걸쳐 요소를 이동(대입)해야 한다.
장점 : 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠르다. 단점 : 삽입할 곳이 멀리 떨어지면 이동(대입)하는 횟수가 많다.
이 알고리즘은 삽입 정렬의 장점을 살리면서 요소들 간의 더 멀리 떨어진 요소들도 비교하여 정렬하려는 시도에서 비롯되었다.
셸 정렬은 다음과 같은 방식으로 동작한다.
먼저 배열을 일정한 간격(셸 정렬에서는 "간격" 또는 "h"라고 함)에 따라 여러 부분 배열로 나눈다.
각 부분 배열에 대해 삽입 정렬을 수행한다. 이때 간격에 따라 떨어진 요소들끼리 삽입 정렬을 수행한다.
간격을 줄여가면서 위의 과정을 반복한다.
간격이 1이 될 때까지 반복. 이때는 일반적인 삽입 정렬이 수행된다.
간격의 선택은 여러 방식이 있으며, 셸 정렬의 성능에 영향을 미친다.
일반적으로는 간격을 반으로 나누어가는 방식이나 Hibbard 간격 등이 사용된다.
이 글에서는 간격을 반으로 나누어가는 방식을 다룬다.
위의 그림은 요솟수가 8개이기 때문에 요솟수의 절반인 4를 첫 번째 간격으로 정한 예제이다.
->이 때 4개의 그룹({8, 7}, {1, 6}, {4, 3}, {2, 5})이 생성되고 각 그룹별로 정렬한다.(4-정렬)
두 번째 간격은 이전의 간격의 절반인 2로 정한다.
->이 때 2개의 그룹({7, 3, 8, 4}, {1, 2, 6, 5})이 생성되고 각 그룹별로 정렬한다.(2-정렬)
이렇게 해서 얻은 배열은 좀 더 정렬된 상태에 가까워진다.
세 번째 간격은 이전의 간격의 절반인 1로 정한다.
마지막으로 간격이 1인 정렬을 적용하면 정렬을 마치게 된다.(1-정렬)
셸 정렬 과정에서 수행하는 각각의 정렬은 h-정렬이라고 한다.
아래의 그림은 h값을 4, 2, 1로 감소시키면서 7회로 정렬을 마치게 된다.
셸 정렬은 비교적 간단하면서도 효과적인 정렬 알고리즘이지만, 정확한 최적 간격을 찾는 것이 어려우며 여러 실험적인 연구가 진행되어왔다.
평균 시간 복잡도는 O(n log^2 n)이지만 최악의 경우에도 O(n^2)으로 다소 비효율적일 수 있다.
셸 정렬은 일반적으로 안정적이지 않다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 셸 정렬 수행
shellSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void shellSort(int[] arr)
{
// 간격(h) 초기화
for (int gap = arr.length / 2; gap > 0; gap /= 2)
{
// 각 부분 배열에 대해 삽입 정렬 수행
for (int i = gap; i < arr.length; i++)
{
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
static void printArray(int[] arr) {
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
퀵 정렬(Quick Sort)
퀵 정렬(Quick Sort)은 불안정하면서도 효율적인 정렬 알고리즘 중 하나이다.
퀵 정렬은 분할 정복(Divide and Conquer) 방법을 기반으로 하며, 배열을 기준 원소(pivot)를 기준으로 두 개의 부분 배열로 분할하고 각 부분 배열을 재귀적으로 정렬하는 방식으로 동작한다.
퀵 정렬의 기본 동작은 다음과 같다.
피벗 선택: 배열에서 하나의 원소를 피벗으로 선택.
파티션(Partitioning): 피벗을 기준으로 작은 요소는 피벗의 왼쪽에, 큰 요소는 피벗의 오른쪽에 배치. 이 과정을 피벗을 중심으로 파티션(분할)이라고 한다.
재귀적으로 정렬: 피벗을 기준으로 파티션된 두 부분 배열에 대해 재귀적으로 퀵 정렬을 수행.
정렬된 부분 배열 병합: 재귀 호출을 통해 얻은 정렬된 부분 배열을 결합하여 전체 배열을 정렬.
배열을 두 그룹으로 나누는 과정은 아래의 그림과 같다.
피벗 이하의 값은 왼쪽으로 이동하고, 피벗 이상의 값은 오른쪽으로 이동한다.
이러한 방식으로 왼쪽 그룹과 오른쪽 그룹에 대해서 재귀적으로 퀵 정렬을 수행하게 된다.
퀵 정렬에서 배열을 나누고 정렬하는 과정을 그림으로 표현하면 아래와 같다.
퀵 정렬은 평균적으로 매우 빠른 성능을 보이며, 평균 시간 복잡도는 O(n log n)이다.
그러나 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있다.
이러한 최악의 경우를 피하기 위해 여러 피벗 선택 전략이나 최적화 기법이 사용될 수 있다.
맨 처음에 언급했듯이 퀵 정렬은 불안정한 정렬 알고리즘이다.
참고로 Arrays.sort() 메소드는 배열에서만 사용 가능하며, 듀얼 피벗 퀵정렬이다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 퀵 정렬 수행
quickSort(myArray, 0, myArray.length - 1);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
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);
}
}
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;
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
병합 정렬(Merge Sort)
병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 정렬하는 효율적인 알고리즘 중 하나이다.
이 알고리즘은 배열을 반으로 나눈 후 각각을 재귀적으로 정렬하고, 정렬된 부분 배열을 합치는 방식으로 동작한다.
병합 정렬의 주요 단계는 다음과 같다.
분할(Divide): 정렬할 배열을 반으로 나눈다. 이 때 중간 지점을 찾아 배열을 두 부분으로 나누게 된다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 병합 정렬 수행
mergeSort(myArray, 0, myArray.length - 1);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void mergeSort(int[] arr, int left, int right)
{
if (left < right)
{
// 중간 지점 계산
int mid = (left + right) / 2;
// 왼쪽 부분 배열 정렬
mergeSort(arr, left, mid);
// 오른쪽 부분 배열 정렬
mergeSort(arr, mid + 1, right);
// 정렬된 부분 배열을 병합
merge(arr, left, mid, right);
}
}
static void merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
// 임시 배열 생성
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// 임시 배열에 데이터 복사
for (int i = 0; i < n1; i++) leftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightArray[j] = arr[mid + 1 + j];
// 두 부분 배열을 합치기
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (leftArray[i] <= rightArray[j])
{
arr[k] = leftArray[i];
i++;
}
else
{
arr[k] = rightArray[j];
j++;
}
k++;
}
// 남은 요소들 복사
while (i < n1)
{
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = rightArray[j];
j++;
k++;
}
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
퀵 정렬과 병합 정렬 차이점
퀵 정렬과 병합 정렬은 둘 다 효율적인 정렬 알고리즘으로, 각각의 장단점이 있다.
분할 정복 방법
퀵 정렬: 피벗을 기준으로 배열을 두 부분으로 분할하고, 각 부분에 대해 재귀적으로 정렬한다.
병합 정렬: 배열을 반으로 나누고, 각 부분에 대해 재귀적으로 정렬한 후 정렬된 부분 배열을 합병한다.
분할 과정의 특징
퀵 정렬: 부분 배열을 피벗을 중심으로 나누어 정렬한다. 부분 배열의 분할은 피벗을 기준으로 작은 값과 큰 값으로 나누는 방식이다.
병합 정렬: 부분 배열을 반으로 나누어 정렬한다. 부분 배열의 분할은 단순히 중간 지점을 선택하여 두 개의 부분으로 나누는 방식이다.
안정성
퀵 정렬: 보통 불안정 정렬에 속한다. 피벗에 의해 상대적인 순서가 변경될 수 있다.
병합 정렬: 안정 정렬에 속한다. 정렬된 부분 배열을 합칠 때 상대적인 순서가 유지된다.
최악의 경우 시간 복잡도:
퀵 정렬: 최악의 경우 시간 복잡도는 O(n^2)이지만, 피벗 선택에 대한 최적화 기법을 사용하면 대부분의 경우에 O(n log n)을 보장한다.
병합 정렬: 항상 O(n log n)이다. 최악의 경우에도 합병 과정에서 추가적인 메모리를 사용하면서 안정적인 성능을 유지한다.
공간 복잡도
퀵 정렬: 일반적으로 추가적인 메모리를 거의 사용하지 않는다. 퀵 정렬은 일반적으로 메모리 효율적이다.
병합 정렬: 추가적인 메모리를 사용하여 병합을 수행한다. 따라서 메모리 사용량이 더 많을 수 있다.
적용 분야
퀵 정렬: 대부분의 실제 상황에서 사용되는 효율적인 정렬 알고리즘 중 하나이다. 특히 데이터의 크기가 큰 경우에 유용하게 적용된다.
병합 정렬: 안정적이면서 일관된 성능을 제공하며, 메모리 사용량이 크게 신경쓰이지 않는 경우에 사용된다. 주로 외부 정렬에 적합하다.
이러한 차이점들을 고려하여 선택해야 하는데, 각 알고리즘은 특정 상황에서 더 유리한 경우가 있다.
힙 정렬(Heap Sort)
힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 하는 정렬 알고리즘이다.
힙은 완전 이진 트리의 일종으로, 부모 노드의 값이 자식 노드의 값보다 항상 큰(또는 작은) 특성을 갖는 자료구조이다.
힙 정렬은 이러한 힙 자료구조의 특성을 이용하여 정렬을 수행한다.
힙 정렬의 주요 단계는 다음과 같다.
힙 구성(Build Heap): 주어진 배열을 힙으로 만든다. 이를 위해 배열의 요소들을 힙의 형태에 맞게 재배치한다. 주로 최대 힙(Max Heap)을 사용하며, 각 노드는 자식 노드보다 큰 값을 가지게 된다.
힙에서 최대값 추출 및 재배치(Extract Max): 최대 힙에서 루트 노드를 추출하여 배열의 뒷부분에 위치시킨다. 그 후 힙의 크기를 감소시키고, 루트 노드에 위치한 값이 힙 특성을 만족하도록 재배치한다. 이 과정을 반복하면서 최대값부터 차례대로 추출한다.
정렬된 배열 구성: 최대값을 추출하면서 배열의 뒷부분에 순서대로 채워나가므로, 최종적으로는 정렬된 배열이 형성된다.
아래의 그림은 힙의 요소를 배열에 저장하는 과정을 나타낸 것이다.
중요한 것은 주어진 배열(정렬할 배열)은 힙이 아닐 가능성이 크다. 우선 주어진 배열을 힙으로 만들어야 한다.
위와 같은 이진 트리가 있다고 가정해보자.
4를 루트로 하는 부분트리(a)는 힙이 아니다.
그러나 왼쪽 자식 8을 루트로 하는 부분트리(b)와 오른쪽 자식 5를 루트로 하는 부분트리(c)는 모두 힙이다.
루트 4를 알맞은 위치로 내려보내면서 부분트리(a)를 힙으로 만들 수 있다.
아래와 같은 방법을 사용하면 아래부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙으로 만들 수 있다.
힙 정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다.
구체적으로 살펴보면 아래와 같은 작업을 반복한다.
힙에서 가장 큰 값인 루트를 꺼낸다.
루트 이외의 부분을 힙으로 만든다.
아래의 내용은 힙에서 가장 큰 값인 루트를 꺼내고 힙 상태를 유지하는 방법을 나타낸다.
아래의 그림은 힙 정렬 알고리즘의 흐름을 나타낸다.
힙 정렬은 평균 및 최악의 경우에도 O(n log n)의 시간 복잡도를 가진다.
이는 힙 구성 단계와 최대값 추출 단계 모두에서 log n의 시간 복잡도가 소요되기 때문이다.
힙 정렬은 추가적인 메모리를 필요로하지 않는 인플레이스(in-place) 정렬 알고리즘 중 하나다.
또한 힙 정렬은 일반적으로 불안정한 정렬 알고리즘이다.
public class Main
{
public static void main(String[] args)
{
int[] myArray = {64, 25, 12, 22, 11};
System.out.println("정렬 전 배열:");
printArray(myArray);
// 힙 정렬 수행
heapSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void heapSort(int[] arr)
{
// 초기 힙 구성
for (int i = arr.length / 2 - 1; i >= 0; i--) heapify(arr, arr.length, i);
// 최대값을 배열의 뒤로 이동하면서 정렬
for (int i = arr.length - 1; i > 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 힙 속성 유지
heapify(arr, i, 0);
}
}
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);
}
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
Counting Sort(계수 정렬)은 정수나 정수 형태로 표현할 수 있는 자료에 대해 매우 빠르게 동작하는 안정적인 선형 시간 정렬 알고리즘 중 하나이다.
특히, 입력 값의 범위가 제한적일 때 효과적으로 동작한다.
Counting Sort의 주요 아이디어는 입력 배열의 각 원소들의 빈도를 세어, 누적 빈도를 이용하여 각 원소가 정렬된 위치를 찾아내는 것이다.
이때, 입력 배열의 원소 값은 정수이며, 각 값은 비교 가능해야 한다.
Counting Sort의 단계는 아래와 같다
빈도수 계산: 입력 배열의 각 원소들의 빈도수(또는 출현 횟수)를 계산.
빈도수 누적: 빈도수를 누적하여, 각 원소의 마지막 위치(또는 정렬된 위치)를 결정.
정렬된 배열 생성: 누적 빈도를 이용하여 입력 배열을 정렬된 배열에 배치.
1. 빈도수 계산
배열 a를 바탕으로 빈도수를 저장하기 위해 배열 f를 사용한다고 가정하자
먼저 배열 f의 모든 요소값을 0으로 초기화한다(0)
그런 다음 배열 a를 처음부터 스캔하면서 빈도수를 계산한다. a[0]은 5이므로 f[5]를 1 증가시켜 1로 만든다.(1)
a[1]은 7이므로 f[7]을 1 증가시켜 1로 만든다(2)
이 작업을 배열 마지막 요소까지 반복하면 빈도수 계산이 완료된다.
f 배열의 인덱스는 a 배열의 요소의 빈도 수를 나타낸다.
2. 빈도수 누적
배열 f의 두 번째 요소부터 바로 앞의 요솟값을 더하는 과정을 진행한다.
가장 마지막에 빈도수 누적이 완료된다.
이 과정을 그림으로 나타내면 아래와 같다.
3. 정렬된 배열 생성
남은 작업은 배열 a의 각 요솟값과 f를 대조하여 정렬을 마친 배열을 마친 배열을 만드는 일이다.
이제 배열 a의 요소를 마지막 요소부터 처음 요소까지 스캔하면서 배열 f와 대조하는 작업을 수행한다.
a[8]의 값은 3이다. f[3]의 값이 5이다. 이때 중요한 작업이 하나있다.
바로 5에서 1을 감소시킨 4를 임시 배열 b의 인덱스로 사용하는 것이다.
즉, 임시 배열인 b[5 - 1]에 a[8]의 값인 3을 저장하는 것이다.
이해가 안간다면, a[7]보자
a[7]의 값은 1이다. f[1]의 값은 2이다.
b[2 - 1]에 a[7]의 값인 1을 저장한다.
a[6]의 과정도 마찬가지이다.
a[6]의 값은 3이다.f[3]의 값은 4이다.
b[4 - 1]에 a[6]의 값인 3을 저장한다.
마지막으로 임시 배열인 b를 a로 복사하면 정렬과정이 끝이 난다.
Counting Sort는 다음과 같은 특징을 가진다.
안정적인 정렬 알고리즘
입력 값의 범위가 작을 때에 가장 효과적으로 동작
입력 배열의 크기가 매우 클지라도 입력 값의 범위에 비례하는 공간 복잡도를 가지므로, 메모리 효율적
public class Main
{
public static void main(String[] args)
{
int[] myArray = {4, 2, 7, 1, 5, 3, 6};
System.out.println("정렬 전 배열:");
printArray(myArray);
// Counting Sort 수행
countingSort(myArray);
System.out.println("\n정렬 후 배열:");
printArray(myArray);
}
static void countingSort(int[] arr)
{
int max = arr[0];
for (int num : arr)
{
if (num > max) max = num;
}
// 빈도수 계산
int[] count = new int[max + 1];
for (int num : arr) count[num]++;
// 빈도수 누적
for (int i = 1; i <= max; i++) count[i] += count[i - 1];
// 정렬된 배열 생성
int[] result = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--)
{
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 원래 배열에 복사
System.arraycopy(result, 0, arr, 0, arr.length);
}
static void printArray(int[] arr)
{
for (int i : arr) System.out.print(i + " ");
System.out.println();
}
}
