Реализация сортировки ведра без использования вектора, указателя и счетной сортировки - PullRequest
Новая
       13

Реализация сортировки ведра без использования вектора, указателя и счетной сортировки

0 голосов
/ 13 ноября 2018

Мы хотим использовать сортировку Bucket для сортировки чисел от 1 до 2001. Количество чисел может быть 10E6.

Я знаю алгоритм сортировки сегментов.Но проблема в том, что в этом вопросе нам не разрешено использовать массив переменной длины, вектор и указатель .(Единственная разрешенная вещь, связанная с указателем, это «передача по ссылке» массива). Единственное решение, которое я нашел, - это использование сортировки с подсчетом для каждого сегмента, как в приведенном ниже коде, поэтому код больше похож на сортировку с подсчетом, чем сортировку с сегментом: (Язык C) 

#include <stdio.h>
int buckets[201][10]={}; int numbers[1000001]={};

void bucket_sort (int a[],int n) {
    for (int i =0;i<=n-1;i++)
    {
        int index = a[i]/10, index2 = a[i]%10;
        buckets[index][index2]++;
    }
    int counter =0;
    for (int i =0;i<=200;i++)
    {
        for (int j =0; j<=9;j++)
        {
            while (buckets[i][j])
            {
                a[counter] = i*10+j; 
                counter++;
                buckets[i][j]--;
            }
        }
    } }

int main() {
    int n;
    scanf("%d",&n);
    if (n==0)
    {
        return 0;
    }
    for (int i =0;i<=n-1;i++)
    {
        scanf("%d",&numbers[i]);
        numbers[i]; 
    }
    bucket_sort(numbers,n);
    for (int i =0;i<=n-1 ;i++)
    {
        printf("%d\n", numbers[i]);
    }
    return 0; }

Я хочу знать, может ли быть реализована сортировка сегментов без массива переменной длины, вектора и указателя, а также без учета сортировки.Вероятно, с использованием Insertion или Bubble sort.Обратите внимание, что это должен быть разумный алгоритм сортировки сегментов.Поэтому определение очень больших сегментов, таких как int bucket [201][1000000];, также является неприемлемым подходом.

1 Ответ

0 голосов
/ 13 ноября 2018

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

void counting_sort(int a[], int n)
{
    int count[2002] = { 0 };
    int i, j; 

    for (i=0; i<n; i++) {
        count[a[i]]++;
    }

    for (i=0, j=0; i<n; i++) {
        while (!count[j]) {
            j++;
        }
        a[i] = j;
        count[j]--;
    }
}
...