изменение основы сортировки по основанию? - PullRequest
Новая
       30

изменение основы сортировки по основанию?

2 голосов
/ 25 апреля 2019

Я пытаюсь разобраться в radix-sort, но у меня возникают проблемы с пониманием меняющихся основ реализации реального кода.Это код, который я использую для изучения radix-сортировки, и я попытаюсь объяснить, что я не понимаю.

Этот код от GeeksForGeeks: 

// C++ implementation of Radix Sort 
#include<iostream> 
using namespace std; 

// A utility function to get maximum value in arr[] 
int getMax(int arr[], int n) 
{ 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > mx) 
            mx = arr[i]; 
    return mx; 
} 

// A function to do counting sort of arr[] according to 
// the digit represented by exp. 
void countSort(int arr[], int n, int exp) 
{ 
    int output[n]; // output array 
    int i, count[10] = {0}; 

    // Store count of occurrences in count[] 
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 

    // Change count[i] so that count[i] now contains actual 
    //  position of this digit in output[] 
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 

    // Build the output array 
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 

    // Copy the output array to arr[], so that arr[] now 
    // contains sorted numbers according to current digit 
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
} 

// The main function to that sorts arr[] of size n using  
// Radix Sort 
void radixsort(int arr[], int n) 
{ 
    // Find the maximum number to know number of digits 
    int m = getMax(arr, n); 

    // Do counting sort for every digit. Note that instead 
    // of passing digit number, exp is passed. exp is 10^i 
    // where i is current digit number 
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 
} 

// A utility function to print an array 
void print(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 

// Driver program to test above functions 
int main() 
{ 
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    radixsort(arr, n); 
    print(arr, n); 
    return 0; 
}

Так чтоПроблема, с которой я столкнулся, заключается в том, что мне нужно иметь сортировку по основанию с переменной базой, где пользователь выбирает свою базу.Насколько я понимаю, основа - это просто представление функции, но я не уверен, как реализовать ее в виде сортировки.Как это повлияет на алгоритм сортировки (вне сложности), если я продолжу использовать базу 10?

1 Ответ

2 голосов
/ 25 апреля 2019

Код у вас есть для базы-10.Каждый раз, когда вы видите жестко закодированный 10 в коде, который должен быть базовым, для его изменения вам нужно будет сделать каждое вхождение динамическим.

Сложность сортировки Radix не зависит от ее базывсегда O (kn) [длина клавиш * n клавиш].Изменение базы помогает уменьшить количество проходов, необходимых для сортировки, но увеличивает количество сегментов, вычисляемых за каждый проход.Кроме этого любая база будет сортировать и давать тот же результат.

...