전에 작성했던 게시물에 전반적으로 어떤 정렬 알고리즘이 있는지 알아봤습니다! 다만, 그렇게 지나가기에는 다소 이해도가 부족한 감이 있어 이를 보충하기 위해서 다양한 알고리즘을 한층 더 알아보고 응용 문제를 풀어보고 이해하는 시간을 가지려고 합니다.
Counting Sort[계수 정렬]
Counting Sort는 O(n)의 시간복잡도를 가진 알고리즘입니다. 기존의 Heap Sort, Quick Sort와 같이 O(nlogn)의 시간복잡도를 가지는 것들과 비교를 했을 경우 상당히 빠르다는 것을 알 수 있습니다. 이렇게 차이가 나는 것은 Quick, Heap Sorting 같은 경우는 직접 비교를 하는 경우가 많습니다. 그렇기 때문에 속도가 O(nlogn)보다 작아질 수 없는 것 입니다.
Process of Sorting
- 주어진 배열(input)의 값과 일치하는 복사한 새로운 배열(counting array)의 값을 1씩 증가시킨다.
대부분의 배열은 이 과정을 거치게 되었을 때 정렬이 되어 출력을 하면됩니다. 하지만, Input 값이 자연수가 아니고 소수의 경우에는 구분이 정화갛게 진행되지 않기 때문에 추가적인 작업을 진행합니다.(만약 소수의 값도 포함해서 정렬을 해야 할 경우에는 Counting Sort가 아닌 Array.sort 등의 다른 알고리즘을 통한 정렬 방식을 사용해야 합니다.)
// Read the number of times
int nTimes = Integer.parseInt(br.readLine());
// Use an array to store frequencies, considering the constraint (<= 10000)
int[] frequencyArray = new int[10001];
// Read the numbers into the array and count frequencies
for (int i = 0; i < nTimes; i++) {
int number = Integer.parseInt(br.readLine());
frequencyArray[number]++;
}- counting array를 처음 부터 누적합을 설정해 줍니다.
이렇게 누적합을 통해서 우리는 본래 배열(input)의 값을 타고 가 counting array의 인덱스로 접근을 하면 Counting array의 key 값에 -1을 한 값이 정렬 결과(output array)를 나타낸다는 것을 알 수 있습니다.(누적합 array를 만듦으로써, 순서가 지정된 시퀸스를 형성합니다.)
// Step 2
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
실제 문제를 푸는 과정에서는 사용하지 않았지만, 정석적인 방법에서는 이와 같이 하는 것이 맞다고 합니다😚 그래서 위의 코드와 약간 맞지 않는 부분이 있을 수 있으나, 이러한 방법이 있다는 것을 보여드리기 위해 코드를 같이 첨부합니다!
- 재정렬
이렇게 위와 같이 정렬이 될 수 있습니다. 그 외에도 현재 예시에는 없지만, 순차적으로 숫자가 나열되어 있지 않고 비어 있는 경우에도 Counting array의 범위가 조금 커지지만 결과를 출력함에 있어 같이 과정을 밟게 되면 올바른 결과를 얻을 수 있습니다.
// Use StringBuilder to buffer the output
StringBuilder output = new StringBuilder();
for (int number = 1; number <= 10000; number++) {
for (int frequency = 0; frequency < frequencyArray[number]; frequency++) {
output.append(number).append('\n');
}
}
// Print the final output
System.out.print(output);여기서 메모리 조건이 없는 경우에는 System.out.println을 사용해도 무방합니다. 다만, StringBuilder를 사용한 이유는 다음과 같습니다.
- 문자열의 불변성
- Java 에서 문자열은 Immutable(불변)입니다. 이는 한 번 문자열이 생성되면 내용을 변경할 수 없기 때문에, 출력하기 위해서 매번 새로운 문자열을 만들어 출력하는 과정에서 불필요하게 할당 및 해제되는 메모리를 아낄 수 있게 됩니다.
- StringBuilder의 가변성
StringBuilder는 가변적으로 설계되어 내부의 내용을 변경할 수 있습니다. 그렇기 때문에 Loop 내에서 새로운 객체를 생성하지 않고 내용을 수정할 수 있습니다.(동적할당 가능)
- 메모리 할당 오버헤드 감소
- 메모리의 불변성에 따라 메모리를 할당하고 해제하는 과정에서 발생하는 추가적인 비용을 나타내는 것이 메모리 할당 오버헤드의 의미입니다. 이러한 오버헤드는 불변성과 가변성의 차이에 의해서 나타나게 됩니다.
위와 같은 이유로 StringBuilder를 사용하여 효율적으로 Sorting을 할 수 있습니다.
Selection Sort[선택정렬]
Selection Sort는 이름 그대로의 성질을 가지고 있습니다. Input array의 각 값을 비교해 가면서 해당 인덱스에 들어갈 데이터를 찾아 선택하는 알고리즘입니다.
해당 알고리즘을 정렬하는 방법은 아래와 같습니다.
- Find min Value in Input Array
- Make min value shift to the start of this array
- Getting swap like step two recursively.
조금 더 직관적으로 이해를 위해서는 아래와 같다고 생각할 수 있습니다.
방금 말씀드린 것 처럼 비교 정렬이며, in-place sort를 하고 있기 때문에 추가적인 메모리를 필요로 하지 않습니다. 그럼 Selection Sort를 구현 해보겠습니다.
public class SelectionSort{
public static void SelectionSort(int[] arr){
int n = arr.length;
for(int i = 0; i < n-1; i++){
int minIndex = i;
for(int j = i+1; j< n; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(arr, minIndex, i);
}
}
public static void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}위와 같이 구현할 수 있습니다. 원래 swap이라는 class는 c++에서 두 수를 비교하기 위해서 존재하지만, 자바에는 존재하지 않기 때문에 따로 만들어서 사용합니다.
Strength and Weakness of Selection Sort
- Strength : 추가적인 메모리 소비가 적습니다.
- Weakness : 시간 복잡도가(O(n^2)) 크고 안정정렬이 아닙니다.
장점은 위에서 이미 언급을 했기 때문에 차치하고 단점에 대해 설명드리겠습니다. Selection Sort는 최솟값을 찾아야 하기 때문에 Input array를 한번 탐색하고 해당 자리와 비교하느 숫자를 찾고 인덱스를 swap하는 과정에서 한번 더 탐색을 하기 때문에 이와 같은 시간 복잡도를 가지게 됩니다.
또한, Stable Sort가 아니라는 것은 정렬하는 결과가 매번 달라질 수 있다는 것을 의미합니다. 예를들어 학생 테이블의 성적을 정리한 테이블을 정렬한다고 했을 때, 동점자가 나온 경우 이름 순으로 정렬을 해야 합니다. 이때, Selection Sort를 사용하게 되면 처음에 정렬한 점수에 대한 정렬만 고려가 되고 이름에 대한 정렬은 이뤄지지 않고 그 해당 결과가 매번 다르게 나올 수 있습니다.
Insertion Sort[삽입 정렬]
Insertion Sort는 단순하게 우리 수중에 있는 카드를 정렬하는 것과 유사한 방법으로 Input array를 정렬하는 알고리즘입니다. 배열을 우선 정렬부와 정렬하지 않은 부분으로 나누고 정렬이 안된 부분에 대한 값을 사이사이 맞는 공간에 삽입합니다. 기본적으로 Ascending order로 정렬을 하게 됩니다.
해당 정렬 알고리즘도 Selection Sort와 비슷하게 비교 정렬이며, in-place sort이기도 합니다. 하지만 이전의 Selction sort와는 다르게 stable sort입니다.
- Compare the current target with the previous index value.
- Swap this target if it's true that target is smaller than the previous one.
- keep following those steps till the end.
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}I thought of putting in the class of
swapto while loop instead but it doesn't satisfy to control to work this code well. that looked too messy.
결과적으로 while문의 코드를 통해서 j를 1씩 줄여가며 만약에 앞에 있는 수들 보다 현재 타켓이 작을 경우 앞으로 보내기 위해서 코드가 구성되어 있습니다. 그래서 이전 원소가 타겟 숫자보다 크기 직전까지 모든 수를 뒤로 한 칸씩 밀어내는 것과 같습니다.
// Java program for implementation of Insertion Sort
public class InsertionSort {
/*Function to sort array using insertion sort*/
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
/* A utility function to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6 };
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr);
}
};
Strength and Weakness of Insetion Sort
- Strength : 추가적인 메모리 소비가 적고 거의 정렬된 경우 O(n)의 시간복잡도를 가질 정도로 효율적인 알고리즘으로써, 게다가 stable sorting이 가능합니다.
- Weakness : 데이터가 역순에 가까울 수록 매우 비효율적이며, 최악의 경우에는 O(n^2)의 시간 복잡도를 가집니다. 그 이유는 previous number 가 target number보다 항상 작기 때문에 n개의 숫자에 대해서 n-1번 비교를 하기 때문입니다.
references
1. Sorting algorithms
2. Insertion Sort
