Radix sort vs Counting sort vs Bucket sort. Какая разница?

Ответ 1

Начнем с некоторого переписывания вашего кода на 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 элементов, прежде всего нулей. Awfully. Чтобы справиться с этой проблемой подсчета сортировки, у нас есть два возможных способа обобщения:

1) Первый способ - сделать сортировку поразмерно. Это называется radix-sort. Давайте покажем некоторый код, пытаясь сделать его максимально приближенным к методу подсчета. Снова посмотрим на комментарии:

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 * O (N) и 7 * O (N) соответственно. Итак, мы приходим ко второму обобщению:

2) Второй способ - сделать ведра более сложными. Это называется bucket-sort.

Позволяет снова начать с некоторого кода. Я предпочитаю больше кода до философских аргументов. Все еще смотрите на комментарии, они важны.

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;
                }
            }
         }
    }

  /* 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.

Теперь вспомним, что мы видели в коде:

• Сортировка сортировки - простые ведра, простая обработка, служебные данные памяти
• Radix sort - простые ведра, сложная обработка, скорость накладных расходов (и по-прежнему требуется дополнительная статическая память)
• Сортировка ковша - сложные ведра, простая обработка, требует динамической памяти, хорошая в среднем

Радикалы и сортировки ковша, таким образом, являются двумя полезными обобщениями сортировки подсчета. У них много общего с подсчетом и друг с другом, но в каждом случае мы что-то теряем и что-то выигрываем. Разработка программного обеспечения связана с балансом между этими возможностями.

Ответ 2

Radix sort vs Counting sort vs Сортировка ведра. Какая разница?

Сортировка ковша помещает ключи или элементы для сортировки в ведра. Как они являются местами в ведрах, являются произвольными и могут быть частью составного ключа и любого распределения, которое вам нравится. Отдельные ведра, возможно, придется сортировать дальше.

Сортировка в памяти выполняется быстрее, чем сортировка на диске. Однако, если у вас больше данных, чем в памяти, вам нужен другой вариант. Что вы можете сделать, это сортировка ведра, где ведра достаточно малы, чтобы вписаться в память. то есть в каждом ковше имеется большое количество записей. Это можно быстро сортировать отдельно.

Сортировка Radix - это определенный тип сортировки ведра. Он начинается с верхних n-бит или n-цифр и может сортировать эти ведра с помощью сортировки radix и т.д., Пока каждая запись не будет отсортирована.

Подсчет сортировки похож на использование сортировки radix, за исключением того, что вы используете все значение. Вместо записи каждого объекта у него есть ведро для каждого объекта, и он просто подсчитывает количество вхождений. Это хорошо работает, когда у вас ограниченное количество возможных ключей, и у вас много дубликатов.

Ответ 3

Ваш код - простой вариант подсчета сортировки без данных, просто ключей.

Сортировка Radix сортируется на основе этого метода. Проблема с подсчетом сортировки - это требование к памяти: int [] bucket=new int[maxVal+1];. Эта проблема решена Radix. Идея состоит в том, чтобы использовать счетную сортировку несколько раз, сначала для более низких цифр, а затем для более высоких. Например, для сортировки 32-разрядных целых чисел, которые вы можете использовать:

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

Это работает, потому что сортировка сортировки стабильна - она ​​хранит порядок данных с равными ключами. Это похоже на сортировку в электронной таблице: sort by B; sort by A дает вам элементы, отсортированные по A, а через B, когда As равны.

Сортировка ковша - это обобщение сортировки подсчета. Вы можете использовать его для сортировки реальных чисел из некоторого предсказуемого распределения вероятностей (например, равномерный (0,1)). Идея состоит в том, чтобы использовать сортировку counting (используя floor(x*N_BUCKETS) как ключ), а затем сортировать только каждый ведро независимо.

Ответ 4

Согласно Geekviewpoint:

Radix: http://www.geekviewpoint.com/java/sorting/radixsort

Сортировка Radix, например сортировка сортировки и сортировка ведра, представляет собой целочисленный алгоритм (т.е. значения входного массива считаются целыми). Следовательно, сортировка radix является одним из самых быстрых алгоритмов сортировки вокруг, теоретически. Особое различие для сортировки по методу радикса состоит в том, что он создает ведро для каждого шифра (например, цифру); как таковой, подобно сортировке ведра, каждый ковш в сортировке по принципу радикса должен быть составленным списком, который может принимать разные ключи.

Ведро: http://www.geekviewpoint.com/java/sorting/bucketsort

Сортировка ведра на самом деле очень хорошая, учитывая, что сортировка счета разумно говорит о ее верхней границе. И подсчет сортировки происходит очень быстро. Особым отличием сортировки ведра является то, что он использует хеш-функцию для разделения ключей входного массива, так что несколько ключей могут хешировать в одном и том же ковше. Следовательно, каждое ведро должно быть эффективным составом; аналогично сортировке по методу radix.

Подсчет: http://www.geekviewpoint.com/java/sorting/countingsort

Особым отличием сортировки счета является то, что он создает ведро для каждого значения и сохраняет счетчик в каждом ковше. Затем каждый раз, когда значение встречается во входной коллекции, соответствующий счетчик увеличивается. Поскольку подсчет сортировки создает ведро для каждого значения, внушительное ограничение заключается в том, что максимальное значение во входном массиве должно быть заранее известно.

Они объясняют это более подробно на своем сайте.

Edit:

• Если вы используете сортировку radix и ваши числа десятичные, вам нужно 10 ведер, по одному для каждой цифры от 0 до 9.

• Если вы используете сортировку counting, вам нужен ведро для каждого уникального значения на входе (на самом деле вам нужен ведро для каждого значения от 0 до max).

• Если вы используете bucketsort, вы не знаете, сколько ведер вы будете использовать. Какую бы хэш-функцию вы не использовали, будет определяться количество ведер.

Ответ 5

Во-первых, давайте посмотрим на разницу между сортировкой Radix и Bucket Sort, потому что это, как правило, путаница, потому что идея кажется одинаковой. Затем мы смотрим на Counting Sort, который похож на основную версию этих двух и какие проблемы с сортировкой подсчета вызывают использование двух других

Начальный проход как для сортировки Radix, так и для Bucket одинаковый. Элементы помещаются в "Ведра", т.е. 0-10, 11-20,... и так далее, в зависимости от количества цифр в наибольшем, т.е. радиуса. В следующем проходе, однако, сортировка ковша упорядочивает эти "ведра" и добавляет их в один массив. Тем не менее, метод сортировки по методу radix добавляет ведра с последующей сортировкой, а "re-buckets" - на основе второй цифры (десяти) номеров. Следовательно, сортировка ковша более эффективна для массивов "Плотный", в то время как Radix Sort может хорошо обрабатывать разреженные массивы. Хорошо подумайте о сортировке ковша, как это

Предположим, что у вас есть список из n записей, каждый с ключом, из числа от 1 до k (мы немного обобщаем проблему, так что k не обязательно равно n).

Мы можем решить это, создав массив связанных списков. Мы перемещаем каждую входную запись в список в соответствующей позиции массива, затем объединяем все списки вместе по порядку.

 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
    }

Что делать, когда k велико? Подумайте о десятичном представлении числа   x = a + 10 b + 100 c + 1000 d +... где a, b, c и т.д. все в диапазоне 0..9. Эти цифры достаточно малы, чтобы сделать сортировку в виде ковша.

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

или более просто

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

Почему мы делаем сначала наименьшую цифру? Если уж на то пошло, почему мы делаем больше, чем один сортимент ковша, так как последний - тот, который ставит все на свои места? Ответ. Если мы пытаемся сортировать вещи вручную, мы склонны делать что-то другое: сначала сделайте сортировку в виде ведра, а затем рекурсивно отсортируйте значения, разделяющие общую первую цифру. Это работает, но менее эффективно, так как оно разбивает проблему на многие подзадачи. Напротив, сортировка radix никогда не разбивает список; он просто применяет сортировку ковша несколько раз в том же списке. При сортировке по основанию последний проход сортировки ковша является самым результативным в общем порядке. Поэтому мы хотим, чтобы он был одним из самых важных цифр. Предыдущие проходы сортировки ковша используются только для того, чтобы позаботиться о случае, когда два элемента имеют один и тот же ключ (mod 10) на последнем проходе.

Теперь, когда у нас есть все, что делает счетчик, он сохраняет вспомогательный массив C с k элементами, все инициализируются 0.

Проведем один проход через входной массив A и для каждого элемента я из A что мы видим, мы увеличиваем C [i] на 1. После того, как мы перебираем через n элементов A и обновления C, значение в индексе j из C соответствует сколько раз j появилось в A. Этот шаг забирает время O (n) для итерации через A. После того, как мы имеем C, мы можем построить отсортированную версию A на итерации через C и вставки каждого элемента j в общей сложности C [j] раз в новый список (или сам А). Итерация через C занимает время O (k). конечный результат - это отсортированный A, и для этого потребовалось время O (n + k).

Падение сортировки подсчета состоит в том, что это может быть не слишком практично, если диапазон элементов слишком велик. Например, если диапазон n элементов, которые нам нужно сортировать, составлял от 1 до n 3, то просто создание вспомогательного массива C займет время O (n ^ 3), а сортировка счетчика будет асимптотически хуже, чем сортировка вставки. Это также занимает пространство O (n ^ 3), которое значительно больше любого пространства, используемого любым другим алгоритмом сортировки, который мы изучили до сих пор. Сортировка Radix помогает решить эту проблему путем сортировки элементов по цифре

Примечание. Источники для ответа и дальнейшего чтения:

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

Первый ответ на вопрос: В чем разница между сортировкой ведра и сортировкой по основанию?

Ответ 6

Сортировка Radix использует форму подсчета сортировки как подпрограмму (ok, может использовать, но чаще всего она будет считать сортировку).

Countingsort - это особая форма сортировки ковша, как ответил kasavbere.

И Bucketsort делит ключи на ведра, а затем сортирует ведра индивидуально.

Ответ 7

Чтобы отсортировать массив с помощью сортировки count:

#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;
}

Это просто O(MAX_INPUT), таким образом сортируя по линейному времени. Для сортировки ковша это совсем другое. Вот реализация