Реализация сортировки сегментами и сортировки подсчетом без использования динамического выделения памяти

Я практиковался в алгоритмах сортировки на С++, и я должен был реализовать алгоритмы без использования векторов. Таким образом, размер несортированного массива может быть определен в начале #define ARR_SIZE 25, а элементы выбираются из равномерно распределенных случайных чисел.

void Sorters::InitializeArray()
{
for (int i = 0; i < ARR_SIZE; i++) {
    arr[i] = uniformRandom.RandomlyDistribute(LOWER_ARRAY_LIMIT, UPPER_ARRAY_LIMIT);
    }
}

Нижняя граница случайного #define LOWER_ARRAY_LIMIT 0, а верхняя граница #define UPPER_ARRAY_LIMIT 200. Я реализовал сортировку пузырьком, которая

void Sorters::BubbleSort(int arr[], int arraySize)
{
for (int k = 0; k < arraySize; k++)
    for (int i = 0; i < arraySize - k - 1; i++)
        if (arr[i] > arr[i + 1]) {
            temporaryVal = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temporaryVal;
        }
}

Однако у меня проблемы с сортировкой ведра и сортировкой подсчетом. Как я могу их реализовать? В Bucket Sort, как я буду определять размер каждого сегмента, поскольку он не является динамическим? Спасибо.


c++ sorting algorithm counting-sort bucket-sort
person Metalian    schedule 06.11.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ведро-сортировка:

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

bucket_sort_int(arr, lower, upper, bit):
    if bit == -1:
        return
    
    l, u = lower, upper
    while l < u:
        if ~bitmask(bit) & arr[l]:
            l++
        else if bitmask(bit) & arr[u]:
            u--
        else:
            arr[l], arr[u] = arr[u], arr[l]
            l++
            u--

    bucket_sort_int(arr, lower, u, bit - 1)
    bucket_sort_int(arr, u + 1, upper, bit - 1)

bucket_sort(arr):
    bucket_sort_int(arr, 0, len(arr) - 1, sizeof(arr[0]) * 8 - 1)

По сути, просто разделите массив по старшему биту, отсортируйте каждый из разделов по следующему старшему биту и рекурсивно примените это, пока весь массив не будет отсортирован.

Сортировка подсчетом:
Диапазон возможных значений в arr в любом случае должен быть известен заранее. Так что в любом случае нет необходимости использовать динамический массив для этого. Просто используйте глобальный массив предопределенной длины и стандартный алгоритм, и все готово.

person Paul    schedule 07.11.2020
comment
Спасибо за ответ. Извините, но поскольку я новичок, мне нужно спросить, как использовать ~bitmask. У вас есть небольшой пример, если бы я собирался использовать ~ битовую маску (бит) и битовую маску (бит). Кроме того, с точки зрения типа данных, каким должен быть тип бита? @Павел - person Metalian; 07.11.2020
comment
@Metalian bitmask(n) - это просто битовая маска для бита n. Так что в основном bitmask(n) = 1 << n. Также обратите внимание, что я изменил bucket_sort в приведенном выше коде. bit теперь sizeof(arr[0]) * 8 - 1. - person Paul; 07.11.2020