기수 정렬 대 계수 정렬 대 버킷 정렬.

기수 정렬 대 계수 정렬 대 버킷 정렬. 차이점이 뭐야?

---

기수, 계산 및 버킷 정렬의 정의를 읽고 있는데 모두 아래 코드에 불과한 것 같습니다.

public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}

내가 옳지 않다는 것을 알고 있는데 내가 뭘 놓치고 있는가? Java 또는 C로 설명하는 데 도움이 될 수 있다고 생각되면 코드를 보여주십시오.

---

C로 코드를 다시 작성하는 것으로 시작하겠습니다. C가 설명하기에 더 익숙하기 때문입니다. 따라서 몇 가지 주석으로 코드를 기억하십시오.

int
counting_sort(int a[], int a_len, int maxVal)
{
  int i, j, outPos = 0;
  int bucket_len = maxVal+1;
  int bucket[bucket_len]; /* simple bucket structure */

  memset(bucket, 0, sizeof(int) * bucket_len);

  /* one loop bucket processing */
  for (i = 0; i < a_len; i++)
    {
      bucket[a[i]]++; /* simple work with buckets */
    }

  for (i=0; i < bucket_len; i++)
    {
      for (j = 0; j < bucket[i]; j++)
        {
          a[outPos++] = i;
        }
    }

  return 0;
}

이제이 사람에게 현실적인 데이터를 제공하겠습니다.

[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]

출력에서 우리는

[126, 171, 201, 223, 316, 343, 348, 432, 556, 670]

모든 것이 괜찮은 것 같습니까? 아직. maxVal을 살펴 보겠습니다. 670 (!)입니다. 여기서 10 개 요소의 배열을 정렬하기 위해 670 개 요소의 배열, 주로 0을 사용했습니다. 몹시. 이 계산 정렬 문제를 처리하기 위해 가능한 두 가지 일반화 방법이 있습니다.

1) 첫 번째 방법-숫자 단위로 정렬합니다. 이를 기수 정렬이라고합니다. 가능한 한 카운팅 정렬 코드에 가깝게 만드는 코드를 보여 드리겠습니다. 다시 주석을보십시오.

int
radix_sort(int a[], int a_len, int ndigits)
{
  int i;
  int b[a_len];
  int expn = 1;

  /* additional loop for digits */
  for (i = 0; i != ndigits; ++i)
    {
      int j;
      int bucket[10] = {0}; /* still simple buckets */

      /* bucket processing becomes tricky */
      for (j = 0; j != a_len; ++j)
        bucket[ a[j] / expn % 10 ]++;

      for (j = 1; j != 10; ++j)
        bucket[j] += bucket[j - 1];

      for (j = a_len - 1; j >= 0; --j)
        b[--bucket[a[j] / expn % 10]] = a[j];

      for (j = 0; j != a_len; ++j)
        a[j] = b[j];

      expn *= 10;
    }
}

우리는 N 근처의 승수를 메모리로 거래하고 있습니다. 이익? 아마도. 그러나 어떤 경우에는 N에 가까운 승수가 매우 중요합니다. 프로그램, 1 일 근무, 1 주일 근무는 각각 1 * O (N), 7 * O (N) 모두 작업하더라도 사용자가 보는 것과는 매우 다릅니다. 그래서 우리는 두 번째 일반화에 도달합니다.

2) 두 번째 방법-버킷을 더 정교하게 만드는 것. 이를 버킷 정렬이라고합니다.

몇 가지 코드로 다시 시작하겠습니다. 나는 철학적 주장보다 더 많은 코드를 선호합니다. 여전히 댓글을 보면 필수입니다.

int
bucket_sort(int a[], int a_len, int maxVal)
{
  int i, aidx;

  typedef struct tag_list {
    int elem;
    struct tag_list *next;
  } list_t, *list_p;

  list_p bucket[10] = {0}; /* sophisticated buckets */

  /* one loop simple processing with one more inner loop 
    to get sorted buckets (insert-sort on lists, Cormen-style) */
  for (i = 0; i != a_len; ++i)
    {
      int bnum = (10 * a[i]) / maxVal;
      list_p bptr = bucket[bnum];
      list_p belem = malloc(sizeof(list_t));
      belem->elem = a[i];
      if (bptr == 0)
        {
          bucket[bnum] = belem;
          belem->next = 0;
          continue;
        }
      else if (a[i] <= bptr->elem)
        {
          belem->next = bptr;
          bucket[bnum] = belem;
          continue;
        }
      else
        {
          while (bptr != 0)
            {
              if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
                {
                  belem->next = bptr->next;
                  bptr->next = belem;
                  break;
                }
               bptr = bptr->next;
            }
         }
    }

  /* one loop (looks as two) to get all back */
  aidx = 0;

  for (i = 0; i != 10; ++i)
    {
      list_p bptr = bucket[i];
      while (bptr)
        {
          list_p optr = bptr;
          a[aidx] = bptr->elem;
          aidx += 1;
          bptr = bptr->next;
          free(optr);
        }
    }

  return 0;
}

그래서 우리는 여기에 무엇을 가지고 있습니까? 우리는 동적으로 할당 된 메모리에 대한 정교한 버킷 구조와 요구 사항을 거래하고 있지만 정적 메모리를 얻고 평균 N에 가까운 승수를 얻습니다.

이제 코드에서 무엇을 봤는지 기억해 보겠습니다.

1. 계산 정렬-단순 버킷, 단순 처리, 메모리 오버 헤드
2. 기수 정렬-간단한 버킷, 정교한 처리, 속도 오버 헤드 (여전히 추가 정적 메모리 필요)
3. 버킷 정렬-정교한 버킷, 간단한 처리, 평균적으로 우수한 동적 메모리 필요

따라서 기수 및 버킷 정렬은 계수 정렬의 두 가지 유용한 일반화입니다. 그들은 계수 정렬과 서로 공통점이 많지만 모든 경우에 우리는 무언가를 잃고 무언가를 이기고 있습니다. 소프트웨어 엔지니어링은 이러한 기회 간의 균형에 관한 것입니다.

---

기수 정렬 대 계수 정렬 대 버킷 정렬. 차이점이 뭐야?

버킷 정렬은 정렬 할 키 또는 요소를 버킷으로 배치합니다. 버킷의 위치는 임의적이며 복합 키 및 원하는 배포의 일부가 될 수 있습니다. 개별 버킷을 추가로 정렬해야 할 수 있습니다.

메모리 정렬은 디스크 정렬보다 빠릅니다. 그러나 메모리 용량보다 많은 데이터가있는 경우 다른 옵션이 필요합니다. 할 수있는 것은 버킷 정렬입니다. 버킷이 메모리에 들어갈만큼 충분히 작습니다. 즉, 각 버킷에 많은 항목이 있습니다. 개별적으로 빠르게 정렬 할 수 있습니다.

기수 정렬은 특정 유형의 버킷 정렬입니다. 상위 n 비트 또는 n 자리로 시작하여 모든 항목이 정렬 될 때까지 기수 정렬 등을 사용하여 해당 버킷을 정렬 할 수 있습니다.

계수 정렬은 전체 값을 사용하는 것을 제외하고는 기수 정렬을 사용하는 것과 같습니다. 각 개체를 기록하는 대신 각 개체에 대한 버킷이 있으며 발생 횟수 만 계산합니다. 이것은 가능한 키의 수가 제한되어 있고 중복이 많은 경우에 잘 작동합니다.

---

Geekviewpoint에 따르면 :

기수 : http://www.geekviewpoint.com/java/sorting/radixsort

계수 정렬 및 버킷 정렬과 같은 기수 정렬은 정수 기반 알고리즘입니다 (즉, 입력 배열의 값은 정수로 간주 됨). 따라서 기수 정렬은 이론상 가장 빠른 정렬 알고리즘 중 하나입니다. 기수 정렬의 특별한 차이점은 각 암호 (즉, 숫자)에 대한 버킷을 생성한다는 것입니다. 따라서 버킷 정렬과 유사하게 기수 정렬의 각 버킷은 서로 다른 키를 허용 할 수있는 확장 가능한 목록이어야합니다.

Bucket: http://www.geekviewpoint.com/java/sorting/bucketsort

Bucket sort is actually very good considering that counting sort is reasonably speaking its upper bound. And counting sort is very fast. The particular distinction for bucket sort is that it uses a hash function to partition the keys of the input array, so that multiple keys may hash to the same bucket. Hence each bucket must effectively be a growable list; similar to radix sort.

Counting: http://www.geekviewpoint.com/java/sorting/countingsort

The particular distinction for counting sort is that it creates a bucket for each value and keep a counter in each bucket. Then each time a value is encountered in the input collection, the appropriate counter is incremented. Because counting sort creates a bucket for each value, an imposing restriction is that the maximum value in the input array be known beforehand.

They explain it in more details on their site.

Edit:

• If you are using radix sort and your numbers are decimal, then you need 10 buckets, one for each digit from 0 to 9.

• If you are using counting sort, then you need a bucket for each unique value in the input (actually you need a bucket for each value between 0 and max).

• If you are using bucketsort, you don't know how many buckets you will be using. Whatever hash function you are using will determine the number of buckets.

---

Your code is simple variant of counting sort without data, just keys.

Radix sort is sort based on this method. The problem with counting sort is memory requirement: int [] bucket=new int[maxVal+1];. Radix sort solves this problem. The idea is to use counting sort several times, first for lower digits, then for higher. For example, to sort 32-bit integers you might use:

sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key

It works, because counting sort is stable - it keeps order of data with equal keys. It's like sorting in spreadsheet: sort by B; sort by A gives you elements sorted by A, and by B when As are equal.

Bucket sort is a generalization of counting sort. You can use it to sort real numbers from some predictable probability distribution (eg. uniform (0,1)). The idea is to use counting sort (using floor(x*N_BUCKETS) as key) and then only sort each bucket independently.

---

Firstly lets look at the difference between Radix Sort and Bucket Sort because that is generally a confusing thing because the idea seems the same. Then we look at Counting Sort which is like a primary version of these two and what problems with counting sort cause the other two to be used

The initial pass of both Radix and Bucket sort are the same.The elements are put in 'Buckets' i.e 0-10, 11-20, ...and so on, depending upon the number of digits in the largest no, i.e the radix. In the next pass, however, bucket sort orders up these 'buckets' and appends them into one array. However, the radix sort method appends the buckets with-out further sorting, and 're-buckets' it based on the second digit (ten's place) of the numbers. Hence, Bucket sort is more efficient for 'Dense' arrays, while Radix Sort can handle sparse arrays well. Well think of bucket sort as this

Suppose you have a list of n records each with a key that's a number from 1 to k (we generalize the problem a little so k is not necessarily equal to n).

We can solve this by making an array of linked lists. We move each input record into the list in the appropriate position of the array then concatenate all the lists together in order.

 bucket sort(L)
    {
    list Y[k+1]
    for (i = 0; i <= k; i++) Y[i] = empty
    while L nonempty
    {
        let X = first record in L
        move X to Y[key(X)]
    }
    for (i = 0; i <= k; i++)
    concatenate Y[i] onto end of L
    }

What to do when k is large? Think about the decimal representation of a number x = a + 10 b + 100 c + 1000 d + ... where a,b,c etc all in range 0..9. These digits are easily small enough to do bucket sort.

   radix sort(L):
    {
    bucket sort by a
    bucket sort by b
    bucket sort by c
    ...
    }

or more simply

radix sort(L):
{
while (some key is nonzero)
{
    bucket sort(keys mod 10)
    keys = keys / 10
}
}

Why do we do the sort least important digit first? For that matter, why do we do more than one bucket sort, since the last one is the one that puts everything into place? Answer: If we're trying to sort things by hand we tend to do something different: first do a bucket sort, then recursively sort the values sharing a common first digit. This works, but is less efficient since it splits the problem up into many subproblems. By contrast, radix sorting never splits up the list; it just applies bucket sorting several times to the same list. In radix sorting, the last pass of bucket sorting is the one with the most effect on the overall order. So we want it to be the one using the most important digits. The previous bucket sorting passes are used only to take care of the case in which two items have the same key (mod 10) on the last pass.

Now that we have that out of the way all Counting sort does is it keeps an auxiliary array C with k elements, all initialized to 0.

We make one pass through the input array A and for each element i in A that we see, we increment C[i] by 1. After we iterate through the n elements of A and update C, the value at index j of C corresponds to how many times j appeared in A. This step takes O(n) time to iterate through A. Once we have C, we can construct the sorted version of A by iterating through C and inserting each element j a total of C[j] times into a new list (or A itself). Iterating through C takes O(k) time.The end result is a sorted A and in total it took O(n + k) time to do so.

The downfall of counting sort is that it may not be too practical if the range of elements is too large. For example, if the range of the n elements we need to sort was from 1 to n 3 , then simply creating the auxiliary array C will take O(n^3) time and counting sort will asymptotically do worse than insertion sort. This also takes O(n^3) space which is significant larger than any of space used by any other sorting algorithm we’ve learned so far. Radix sort helps solve this problem by sorting the elements digit by digit

Note: Sources for answer and further reading:

http://htmltolatex.sourceforge.net/samples/sample4.html

The first answer to: What is the difference between bucket sort and radix sort?

---

Radix sort uses a form of counting sort as subroutine (ok, can use, but most often it will be counting sort).

Countingsort is a special form of bucket sort, as kasavbere answered.

And Bucketsort divides the keys into buckets and then sorts the buckets individually.

---

To sort an array using count sort:

#define MAX_INPUT 1000

void sort(int arr[100], int n)
{
    static int hash[MAX_INPUT], i, j;

    memset(hash, 0, sizeof hash);

    for (i = 0; i < n; ++i) ++hash[arr[i]];

    j = 0;
    for (i = 0; i < MAX_INPUT; ++i)
        while (hash[i]--)
           arr[j++] = i;
}

This is just O(MAX_INPUT), thus sorting in linear time. For bucket sort, it is very different. Here is an implementation

ReferenceURL : https://stackoverflow.com/questions/14368392/radix-sort-vs-counting-sort-vs-bucket-sort-whats-the-difference