Java의 버킷 정렬

주어진 배열의 요소를 여러 개의 버킷에 분산시켜 각 버킷을 서로 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 재귀적으로 사용하여 정렬하는 정렬 기술을 Java에서는 공간 복잡도가 O인 버킷 정렬이라고 합니다. (1) 최악의 경우 복잡도는 O(n^2), 최상의 경우 복잡도는 오메가(n+k), 평균 경우의 복잡도는 세타(n+k)이며 배열의 주어진 요소를 정렬하는 버킷 정렬 기술은 다음과 같이 작동합니다. 다른 정렬 알고리즘에 비해 속도가 빠르며 버킷 정렬 알고리즘을 사용하여 정렬할 배열의 요소는 균일하게 분포되어야 합니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

Java에서 버킷 정렬을 수행하는 함수는 다음과 같습니다.

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

여기서 array는 버킷 정렬 알고리즘을 사용하여 정렬할 입력 배열이고 maximum_value는 해당 배열에 존재하는 maximum_value이며 sorted_array는 정렬된 요소로 구성된 결과 배열입니다.

Java의 버킷 정렬 알고리즘 작동

Java에서 버킷 정렬 알고리즘의 작동 방식은 다음과 같습니다.

• 버킷 정렬 알고리즘의 첫 번째 단계는 버킷으로 간주되는 빈 배열을 만드는 것입니다.
• 두 번째 단계는 정렬할 요소가 있는 전체 입력 배열을 순회하고 각 요소를 버킷에 추가하는 것입니다.
• 세 번째 단계는 버킷의 각 요소를 정렬하는 것입니다.
• 네 번째 단계는 버킷의 모든 요소를 ​​순회하고 각 요소를 정렬된 순서로 원래 입력 배열에 추가하는 것입니다.

Java의 버킷 정렬 예

아래 예시는 다음과 같습니다.

예시 #1

버킷 정렬 알고리즘을 구현하여 주어진 배열의 요소를 정렬한 다음 정렬된 배열 요소를 화면에 출력으로 표시하는 Java 프로그램:

 코드:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

출력:

위 프로그램에서는 버킷 배열로 간주되는 newbucket이라는 빈 배열을 생성합니다. 그런 다음 결과 배열을 저장하기 위해 sorted_array라는 또 다른 빈 배열을 만듭니다. 그런 다음 입력 배열을 탐색하여 버킷 배열에 각 요소를 추가합니다. 그런 다음 버킷 배열의 각 요소를 정렬하고 정렬된 각 요소를 원래 입력 배열에 추가합니다. 그런 다음 버킷 정렬 기술을 사용하여 주어진 배열을 정렬하기 위해 입력 배열에서 최대값을 찾는 함수를 정의합니다. 그런 다음 결과 배열을 표시하는 기본 함수가 호출됩니다. 출력은 위의 스냅샷에 표시됩니다.

예시 #2

버킷 정렬 알고리즘을 구현하여 주어진 배열의 요소를 정렬한 다음 정렬된 배열 요소를 화면에 출력으로 표시하는 Java 프로그램:

코드:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

출력:

위 프로그램에서는 버킷 배열로 간주되는 새 버킷이라는 빈 배열을 생성합니다. 그런 다음 결과 배열을 저장하기 위해 sorted_array라는 또 다른 빈 배열을 만듭니다. 그런 다음 입력 배열을 탐색하여 버킷 배열에 각 요소를 추가합니다. 그런 다음 버킷 배열의 각 요소를 정렬하고 정렬된 각 요소를 원래 입력 배열에 추가합니다. 그런 다음 버킷 정렬 기술을 사용하여 주어진 배열을 정렬하기 위해 입력 배열에서 최대값을 찾는 함수를 정의합니다. 그런 다음 결과 배열을 표시하는 기본 함수가 호출됩니다. 출력은 위의 스냅샷에 표시됩니다.

위 내용은 Java의 버킷 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!