logo

TechCodeview

버킷 정렬 알고리즘

이번 포스팅에서는 버킷 정렬 알고리즘에 대해 알아보겠습니다. 버킷 정렬의 데이터 항목은 버킷 형태로 배포됩니다. 소프트웨어 엔지니어를 위한 코딩이나 기술 인터뷰에서 정렬 알고리즘에 대한 질문이 많이 나옵니다. 따라서 주제에 대해 토론하는 것이 중요합니다.

버킷 정렬은 요소를 버킷이라고 하는 여러 그룹으로 분리하는 정렬 알고리즘입니다. 버킷 정렬의 요소는 먼저 버킷이라는 그룹으로 균일하게 분할된 다음 다른 정렬 알고리즘에 따라 정렬됩니다. 그 후, 요소들은 정렬된 방식으로 수집됩니다.

버킷 정렬을 수행하는 기본 절차는 다음과 같습니다.

  • 먼저 범위를 고정된 수의 버킷으로 분할합니다.
  • 그런 다음 모든 요소를 ​​적절한 버킷에 버립니다.
  • 그런 다음 정렬 알고리즘을 적용하여 각 버킷을 개별적으로 정렬합니다.
  • 그리고 마지막으로 정렬된 버킷을 모두 연결합니다.

버킷 정렬의 장점은 다음과 같습니다.

  • 버킷 정렬은 숫자를 줄입니다. 비교의.
  • 요소의 균일한 분포로 인해 점근적으로 빠릅니다.

버킷 정렬의 제한 사항은 다음과 같습니다.

  • 안정적인 정렬 알고리즘일 수도 있고 아닐 수도 있습니다.
  • 큰 배열이 있으면 비용이 증가하므로 유용하지 않습니다.
  • 버킷을 정렬하려면 약간의 추가 공간이 필요하기 때문에 내부 정렬 알고리즘이 아닙니다.

버킷 정렬의 최고 및 평균 사례 복잡성은 다음과 같습니다. O(n + k) , 버킷 정렬의 최악의 복잡성은 다음과 같습니다. 에2) , 어디 N 항목의 개수입니다.

버킷 정렬이 일반적으로 사용됩니다.

  • 부동 소수점 값을 사용합니다.
  • 입력이 범위에 걸쳐 균일하게 분포되는 경우.

버킷 정렬을 수행하는 기본 아이디어는 다음과 같습니다.

 bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort

이제 버킷 정렬 알고리즘을 살펴보겠습니다.

연산

 Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End

분산 수집 방식

분산 수집 방식을 통해 버킷 정렬 알고리즘을 이해할 수 있습니다. 여기서는 주어진 요소가 먼저 버킷에 분산됩니다. 분산 후 각 버킷의 요소는 안정적인 정렬 알고리즘을 사용하여 정렬됩니다. 마지막으로 정렬된 요소가 순서대로 수집됩니다.

버킷 정렬 과정을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 예제를 통해 버킷 정렬을 이해하는 것이 더 쉬울 것입니다.

배열의 요소는 다음과 같습니다.

버킷 정렬

이제 0~25 범위의 버킷을 만듭니다. 버킷 범위는 0-5, 5-10, 10-15, 15-20, 20-25입니다. 버킷 범위에 따라 요소가 버킷에 삽입됩니다. 항목의 값이 16이라고 가정하면 15-20 범위의 버킷에 삽입됩니다. 마찬가지로 배열의 모든 항목이 그에 따라 삽입됩니다.

이 단계는 다음 단계로 알려져 있습니다. 배열 요소의 분산 .

버킷 정렬

지금, 종류 각 버킷을 개별적으로. 각 버킷의 요소는 안정적인 정렬 알고리즘을 사용하여 정렬할 수 있습니다.

버킷 정렬

마침내, 모으다 각 버킷의 요소를 순서대로 정렬합니다.

버킷 정렬

이제 배열이 완전히 정렬되었습니다.

버킷 정렬의 복잡성

이제 최상의 경우, 평균적인 경우, 최악의 경우 버킷 정렬의 시간 복잡도를 살펴보겠습니다. 버킷 정렬의 공간 복잡도도 살펴보겠습니다.

1. 시간 복잡도

사례 시간 복잡성
최선의 경우 O(n + k)
평균 사례 O(n + k)
최악의 경우 에2)
    최상의 경우 복잡성 -정렬이 필요하지 않을 때 발생합니다. 즉, 배열이 이미 정렬되어 있습니다. 버킷 정렬에서는 요소가 버킷에 균일하게 분포될 때 가장 좋은 경우가 발생합니다. 버킷에 요소가 이미 정렬되어 있으면 복잡성이 더 좋아집니다.
    버킷 요소를 정렬하기 위해 삽입 정렬을 사용하면 전체 복잡도는 선형이 됩니다. 즉, O(n + k)입니다. 여기서 O(n)은 버킷을 만들기 위한 것이고 O(k)는 버킷 요소를 정렬하기 위한 것입니다. 최상의 경우 선형 시간 복잡도를 갖는 알고리즘을 사용합니다.
    버킷 정렬의 최상의 경우 시간 복잡도는 다음과 같습니다. O(n + k) .평균 사례 복잡성 -이는 배열 요소가 제대로 오름차순이 아니고 내림차순이 아닌 뒤죽박죽된 순서로 되어 있을 때 발생합니다. 버킷 정렬은 요소가 균일하게 분포된 경우에도 선형 시간에 실행됩니다. 버킷 정렬의 평균 사례 시간 복잡도는 다음과 같습니다. 오(n + K) .최악의 경우 복잡성 -버킷 정렬에서는 요소가 배열 내에서 가까운 범위에 있을 때 최악의 경우가 발생하므로 동일한 버킷에 배치해야 합니다. 따라서 일부 버킷에는 다른 버킷보다 더 많은 요소가 있습니다.
    요소가 역순으로 있으면 복잡성이 더 심해집니다.
    버킷 정렬의 최악의 시간 복잡도는 다음과 같습니다. 에2) .

2. 공간 복잡성

공간 복잡도 오(n*k)
안정적인 예
  • 버킷 정렬의 공간 복잡도는 O(n*k)입니다.

버킷 정렬 구현

이제 다양한 프로그래밍 언어로 작성된 버킷 정렬 프로그램을 살펴보겠습니다.

프로그램: C 언어로 버킷 정렬을 구현하는 프로그램을 작성하세요.

 #include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are - 
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are - 
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are - 
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are - 
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>