버킷 정렬 요소를 다양한 그룹 또는 버킷으로 나누는 정렬 기술입니다. 이러한 버킷은 요소를 균일하게 배포하여 형성됩니다. 요소가 버킷으로 분할되면 다른 정렬 알고리즘을 사용하여 정렬할 수 있습니다. 마지막으로, 정렬된 요소들은 순서대로 모아집니다.
버킷 정렬 알고리즘:
만들다 N 빈 버킷(또는 목록)을 만들고 모든 배열 요소 arr[i]에 대해 다음을 수행합니다.
- 버킷[n*array[i]]에 arr[i]를 삽입합니다.
- 삽입 정렬을 사용하여 개별 버킷을 정렬합니다.
- 정렬된 버킷을 모두 연결합니다.
버킷 정렬은 어떻게 작동하나요?
입력 배열에 버킷 정렬을 적용하려면 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] , 다음 단계를 따릅니다.
1 단계: 각 슬롯이 버킷을 나타내는 크기 10의 배열을 만듭니다.
정렬용 버킷 생성
2 단계: 범위에 따라 입력 배열의 버킷에 요소를 삽입합니다.
버킷에 요소 삽입:
- 입력 배열에서 각 요소를 가져옵니다.
- 요소에 버킷 배열의 크기(이 경우 10)를 곱합니다. 예를 들어 요소 0.23의 경우 0.23 * 10 = 2.3을 얻습니다.
- 결과를 정수로 변환하면 버킷 인덱스가 제공됩니다. 이 경우 2.3은 정수 2로 변환됩니다.
- 계산된 인덱스에 해당하는 버킷에 요소를 삽입합니다.
- 입력 배열의 모든 요소에 대해 이 단계를 반복합니다.
각 버킷에 배열 요소 삽입
3단계: 각 버킷 내의 요소를 정렬합니다. 이 예에서는 빠른 정렬(또는 안정적인 정렬 알고리즘)을 사용하여 각 버킷 내의 요소를 정렬합니다.
각 버킷 내의 요소 정렬:
- 안정적인 정렬 알고리즘(예: 버블 정렬, 병합 정렬)을 적용하여 각 버킷 내의 요소를 정렬합니다.
- 이제 각 버킷 내의 요소가 정렬됩니다.
개별 버킷 정렬
4단계: 각 버킷에서 요소를 수집하여 원래 배열에 다시 넣습니다.
각 버킷에서 요소 수집:
- 각 버킷을 순서대로 반복합니다.
- 버킷의 각 개별 요소를 원래 배열에 삽입합니다.
- 요소가 복사되면 버킷에서 제거됩니다.
- 모든 요소가 수집될 때까지 모든 버킷에 대해 이 프로세스를 반복합니다.
결과 배열에 버킷을 오름차순으로 삽입
5단계: 이제 원래 배열에는 정렬된 요소가 포함됩니다.
주어진 입력에 대해 버킷 정렬을 사용하여 최종 정렬된 배열은 [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]입니다.
정렬된 배열 반환
버킷 정렬 알고리즘 구현:
다음은 버킷 정렬의 구현입니다.
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& 버킷) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && 버킷[j]> 키) { 버킷[j + 1] = 버킷[j]; 제이--; } 버킷[j + 1] = 키; } } // 버킷 정렬을 사용하여 크기 n의 arr[]을 정렬하는 함수 void bucketSort(float arr[], int n) { // 1) n 개의 빈 버킷 벡터 생성b[n]; // 2) 배열 요소를 다른 버킷에 넣습니다 for (int i = 0; i< n; i++) { int bi = n * arr[i]; b[bi].push_back(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(b[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < b[i].size(); j++) { arr[index++] = b[i][j]; } } } // Driver program to test above function int main() { float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; int n = sizeof(arr) / sizeof(arr[0]); bucketSort(arr, n); cout << 'Sorted array is
'; for (int i = 0; i < n; i++) { cout << arr[i] << ' '; } return 0; }>
자바 import java.util.ArrayList; import java.util.List; public class Main { // Insertion sort function to sort individual buckets public static void insertionSort(List버킷) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> key) { bucket.set(j + 1, bucket.get(j)); 제이--; } bucket.set(j + 1, 키); } } // 버킷 정렬을 사용하여 크기 n의 arr[]을 정렬하는 함수 public static void bucketSort(float[] arr) { int n = arr.length; // 1) n개의 빈 버킷 목록을 생성합니다.[] 버킷 = 새로운 ArrayList[n]; for (int i = 0; i< n; i++) { buckets[i] = new ArrayList(); } // 2) Put array elements in different buckets for (int i = 0; i < n; i++) { int bi = (int) (n * arr[i]); buckets[bi].add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].size(); j++) { arr[index++] = buckets[i].get(j); } } } // Driver program to test above function public static void main(String[] args) { float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f}; bucketSort(arr); System.out.println('Sorted array is:'); for (float num : arr) { System.out.print(num + ' '); } } }> 파이썬 def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 및 버킷[j]> 키: 버킷[j + 1] = 버킷[j] j -= 1 버킷[j + 1] = 키 def bucket_sort(arr): n = len(arr) 버킷 = [[] for _ in range(n)] # 배열 요소를 다른 버킷에 넣습니다 for num in arr: bi = int(n * num) buckets[bi].append(num) # 삽입 정렬을 사용하여 개별 버킷을 정렬합니다 for bucket in buckets: insert_sort (bucket) # 모든 버킷을 arr[] index = 0으로 연결 for bucket in buckets: for num in bucket: arr[index] = num index += 1 arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434] bucket_sort (arr) print('정렬된 배열은 다음과 같습니다:') print(' '.join(map(str, arr)))> 씨# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(List버킷) { for (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && 버킷[j]> 키) { 버킷[j + 1] = 버킷[j]; 제이--; } 버킷[j + 1] = 키; } } // 버킷 정렬을 사용하여 크기 n의 arr[]을 정렬하는 함수 static void BucketSort(float[] arr) { int n = arr.Length; // 1) n개의 빈 버킷 목록을 생성합니다.[] 버킷 = 새 목록[N]; for (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) 배열 요소를 서로 다른 버킷에 넣습니다 for (int i = 0; i< n; i++) { int bi = (int)(n * arr[i]); buckets[bi].Add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { InsertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].Count; j++) { arr[index++] = buckets[i][j]; } } } // Driver program to test above function static void Main(string[] args) { float[] arr = { 0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f }; BucketSort(arr); Console.WriteLine('Sorted array is:'); foreach (float num in arr) { Console.Write(num + ' '); } } }> 자바스크립트 function insertionSort(bucket) { for (let i = 1; i < bucket.length; ++i) { let key = bucket[i]; let j = i - 1; while (j>= 0 && 버킷[j]> 키) { 버킷[j + 1] = 버킷[j]; 제이--; } 버킷[j + 1] = 키; } } function bucketSort(arr) { let n = arr.length; let buckets = Array.from({length: n}, () => []); // 배열 요소를 서로 다른 버킷에 넣습니다 for (let i = 0; i< n; i++) { let bi = Math.floor(n * arr[i]); buckets[bi].push(arr[i]); } // Sort individual buckets using insertion sort for (let i = 0; i < n; i++) { insertionSort(buckets[i]); } // Concatenate all buckets into arr[] let index = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < buckets[i].length; j++) { arr[index++] = buckets[i][j]; } } } let arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]; bucketSort(arr); console.log('Sorted array is:'); console.log(arr.join(' '));> 산출
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
버킷 정렬 알고리즘의 복잡성 분석:
시간 복잡도: 에2),
- 버킷에 삽입하는 데 O(1) 시간이 걸린다고 가정하면 위 알고리즘의 1단계와 2단계에는 분명히 O(n) 시간이 걸립니다.
- 버킷을 표현하기 위해 연결 목록을 사용하면 O(1)이 쉽게 가능합니다.
- 4단계에서도 모든 버킷에 n개의 항목이 있으므로 O(n) 시간이 걸립니다.
- 분석의 주요 단계는 3단계입니다. 이 단계 역시 모든 숫자가 균일하게 분포된 경우 평균 O(n) 시간이 걸립니다.
보조 공간: 오(n+k)