Реализация сортировки сегментов

Я должен реализовать сортировку ведра, чтобы он сортировал массив с size = 100 со случайно сгенерированными числами от 0 до 100. Мои ведра следующие:

Bucket0: (0<=x<10)
Bucket1: (10<=x<20)
.
.
.
Bucket9: (90<=x<100)

Теперь я понимаю теорию сортировки ведра, когда я вставляю элементы в каждое отдельное ведро, но чего я не понимаю, как на самом деле создавать ведра. Я создаю массив, скажем, B с самими ведрами, являющимися массивами? Или это более стандартный способ реализации сортировки ведра с целыми числами?

Мне просто нужен толчок в правильном направлении, спасибо за любую помощь!


c++ arrays sorting bucket-sort
person zsloan112    schedule 13.10.2017    source источник
comment
Вы должны показать свои усилия, чтобы решить эту проблему. Если вам нужно наставничество или коучинг, попробуйте такие сервисы, как Codementor, Savvy, Hackhands или airpair.   -  person tadman    schedule 13.10.2017
comment
Какой вариант групповой сортировки следует использовать для этого задания?   -  person rcgldr    schedule 14.10.2017
comment
Это никогда не указывалось, все, что было сказано, это сортировать каждое ведро с помощью сортировки вставками. На самом деле я смог получить исходный массив в 2D-массив, где каждая строка была ведром, теперь мне просто нужно выяснить, как выполнить сортировку вставками для каждой строки.   -  person zsloan112    schedule 14.10.2017

Ответы (1)


arrow_upward
1
arrow_downward

Да.
Вам нужно объявить другой массив (можно сказать, b) длиной 101. Длина представляет собой диапазон наших чисел.

Теперь вам нужно перебрать первый массив и каждую ячейку, и когда вы найдете каждое число k (0 ‹= k ‹= 100) , вам нужно ++ b[k]. Что-то вроде: b[a[i]]++;

Теперь у нас есть массив b, который показывает, сколько раз каждое число k встречалось в первом массиве. Мы можем переопределить первый массив:

for(int i = 0; i <= RANGE; i++)
    for(int j = 0; j < b[i]; j++)
        a[p++] = i;

В вашем случае RANGE равен 100.

Сложность: O(n)

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

person Yinon    schedule 13.10.2017
comment
Это сортировка подсчетом , которую можно рассматривать как один из вариантов групповая сортировка . В ОП не указано, какой вариант сортировки ведра следует использовать. - person rcgldr; 14.10.2017