가장 빠른 정렬 알고리즘 Java
이 기사에서는 두 가지 가장 빠른 정렬 알고리즘을 다루고 Java로 코드를 작성합니다.
첫 번째 기술은 몇 가지 제한 사항이 있는 Counting Sort입니다. 따라서 병합 정렬 알고리즘도 다룰 것입니다.
Java의 정렬 알고리즘 계산
카운팅 정렬 알고리즘은 배열 요소가 특정 범위 내에서 제공될 때 사용할 수 있는 가장 빠른 정렬 기술 중 하나입니다. 비교 기반 정렬 방식이 아니라 모든 배열 요소의 빈도를 세고 저장하여 배열을 정렬합니다.
간단히 말해서 해싱을 사용하여 배열을 정렬합니다.
사용자는 카운팅 정렬을 위해 아래 알고리즘을 따라야 합니다.
-
배열의 최대 및 최소 요소를 찾습니다.
-
다음으로 최대 및 최소 요소를 사용하여 배열의 범위를 찾고 크기 범위의 새
freq배열을 만들어 모든 요소의 빈도를 저장합니다. -
원래 배열을 반복하고
freq배열의 모든 요소의 빈도를 저장합니다. -
주파수를 추가하여 모든 요소에 대한 누적 빈도를 계산합니다.
-
끝에서 원래 배열로 반복을 시작하고
freq배열을 사용하여 모든 요소를 정렬된 위치에 놓습니다. -
result에서 정렬된 모든 요소를 원래 배열에 저장하여 원래 배열을 정렬합니다.
예제 코드:
class CountingSort {
// function to find the maximum from the array
static int findMax(int arr[]) {
int maxi = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxi)
maxi = arr[i];
}
return maxi; // return maximum
}
// function to find the minimum from the array
static int findMin(int arr[]) {
int mini = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < mini)
mini = arr[i];
}
return mini; // return minimum
}
static void cntSort(int[] arr) {
int maxi = findMax(arr);
int mini = findMin(arr);
// getting range from maximum and minimum elements of the array
int range = maxi - mini + 1;
// creating the array to store the frequency of elements
int freq[] = new int[range];
// resultant array
int result[] = new int[arr.length];
// counting frequency of elements and storing it to freq array
for (int i = 0; i < arr.length; i++) {
freq[arr[i] - mini]++;
}
// Doing addition of frequency
for (int i = 1; i < freq.length; i++) {
freq[i] += freq[i - 1];
}
// Putting every element of arr to its correct place based on the freq array
for (int i = arr.length - 1; i >= 0; i--) {
result[freq[arr[i] - mini] - 1] = arr[i];
freq[arr[i] - mini]--;
}
// Make arr array sorted by assigning elements from the result array
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 20, -2, -4, 3, 40, 50, 30, 20, 10};
cntSort(arr);
System.out.println("Sorted Array using counting sort is ");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
출력:
Sorted Array is -4 -2 3 10 10 20 20 30 40 50
Java에서 카운팅 정렬 알고리즘의 시간 복잡도
Counting Sort의 시간 복잡도는 단일 for 루프를 사용하므로 선형 순서입니다.
| 최상의 경우 | O(n+k) |
| 평균 사례 | O(n+k) |
| 최악의 경우 | O(n+k) |
Java에서 카운팅 정렬 알고리즘의 공간 복잡도
카운팅 정렬의 공간 복잡도는 O(n)입니다. 정렬된 요소를 저장하기 위해 임시 배열을 사용하기 때문입니다.
Java의 카운팅 정렬 알고리즘의 한계
카운팅 정렬 기술은 의심할 여지 없이 배열의 요소를 정렬하는 가장 빠른 알고리즘이지만 몇 가지 제한 사항이 있습니다.
사용자는 배열 길이가 매우 작고 입력 범위가 수백만과 같이 너무 큰 시나리오에 대해 생각할 수 있습니다. 이러한 경우에는 버블 정렬도 더 잘 수행할 수 있습니다.
따라서 사용자는 입력 범위가 작을 때 선형 시간으로 배열을 정렬하는 데 사용할 수 있습니다.
Java의 병합 정렬 알고리즘
Counting Sort의 한계를 극복하기 위해 사용자는 Merge Sort 기술을 사용할 수 있습니다.
병합 정렬 알고리즘은 분할 정복 방식을 따릅니다. 먼저 배열을 반으로 나누고 정렬한 다음 정렬된 배열을 병합합니다.
전체 알고리즘을 단계별로 학습하기 위해 사용자는 아래 단계를 따를 수 있습니다.
-
배열의 중간 지점을 찾습니다.
-
배열의 첫 번째 부분과 두 번째 부분에 대해
mergeSort()함수를 재귀적으로 호출합니다. -
merge()함수를 호출하여 배열을 병합합니다. -
merge()함수에서 배열의 두 부분과 같은 크기의 임시 배열 두 개를 만들고 배열 요소를 해당 임시 배열에 저장합니다. -
둘 다 정렬되지 않은 요소를 가질 때까지 임시 배열을 반복하고 두 배열에서 최소 요소를 찾아 원래 배열에 저장하고 계속 이동합니다.
-
LeftArray에 요소가 남아 있으면 원래 배열에 저장하고RightArray에 대해 동일한 작업을 수행합니다.
예제 코드:
class Test {
// function to merge two sorted arrays
static void merge(int arr[], int left, int mid, int right) {
// sizes for temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
// temp arrays
int LeftArray[] = new int[n1];
int RigthArray[] = new int[n2];
// clone data to temp arrays
for (int i = 0; i < n1; ++i) LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j) RigthArray[j] = arr[mid + 1 + j];
int a = 0, b = 0;
// merging temp arrays to the original array
int k = left;
while (a < n1 && b < n2) {
if (LeftArray[a] <= RigthArray[b]) {
arr[k] = LeftArray[a];
a++;
} else {
arr[k] = RigthArray[b];
b++;
}
k++;
}
// If any elements are left in LeftArray, clone it to the original array
while (a < n1) {
arr[k] = LeftArray[a];
a++;
k++;
}
// If any elements are left in RightArray, clone it to the original array
while (b < n2) {
arr[k] = RigthArray[b];
b++;
k++;
}
}
static void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the mid of the array using the left and right
int mid = left + (right - left) / 2;
// sort the first half of the array
mergeSort(arr, left, mid);
// sort the second half of the array
mergeSort(arr, mid + 1, right);
// sort both parts of the array and merge it
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int[] arr = {10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using merge sort is");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
출력:
Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212
Java 병합 정렬 알고리즘의 시간 복잡도
mergeSort()의 시간 복잡도는 O(nlogn)이며 n은 배열의 길이입니다. 여기에서 merge() 함수의 시간 복잡도는 O(n)이고 mergeSort() 함수의 시간 복잡도는 O(logn)입니다. 배열의 절반 부분.
| 최상의 경우 | O(nlog(n)) |
| 평균 사례 | O(nlog(n)) |
| 최악의 경우 | O(nlog(n)) |
Java 병합 정렬 알고리즘의 공간 복잡도
정렬되지 않은 요소를 저장하기 위해 두 개의 임시 배열을 사용하므로 병합 정렬의 공간 복잡도는 O(n)입니다.
이 기사에서는 Java에서 가장 빠른 알고리즘 중 하나인 카운팅 정렬 알고리즘을 예제 코드와 함께 단계별로 학습했습니다. 또한 카운팅 정렬의 한계를 극복하기 위해 모든 입력 범위에 대해 작동하는 병합 정렬을 배웠습니다.
