Holleriths Radixsort

Question

ich die normale Radix Sort implementiert haben:

#include <iostream> 

using namespace std; 

void print(int arr[], int n) { 
    for (int i = 0; i < n; i++) { 
     cout << arr[i] << " "; 
    } 
    cout << endl; 
} 

int findMax(int arr[], int n) { 
    int mx = 0; 
    for (int i = 0; i < n; i++) { 
     if (arr[i] > mx) 
      mx = arr[i]; 
    } 
    return mx; 
} 

void countingSort(int arr[], int n, int exp) { 
    int output[n]; 
    const int m = findMax(arr, n) + 1; 
    int C[m]; 
    for (int i = 0; i < m; i++) { 
     C[i] = 0; 
    } 

    for (int i = 0; i < n; i++) 
     C[(arr[i]/exp) % 10]++; 

    for (int i = 1; i < 10; i++) 
     C[i] += C[i - 1]; 

    for (int i = n - 1; i >= 0; i--) { 
     output[C[(arr[i]/exp) % 10] - 1] = arr[i]; 
     C[(arr[i]/exp) % 10]--; 
    } 

    for (int i = 0; i < n; i++) 
     arr[i] = output[i]; 
} 

void radixSotr(int arr[], int n) { 
    int m = findMax(arr, n); 
    for (int exp = 1; m/exp > 0; exp *= 10) { 
     countingSort(arr, n, exp); 
    } 
} 

int main() { 
    int n; 
    cout << "Enter the number of elements: "; 
    cin >> n; 
    int arr[n]; 
    cout << "Enter the elements of the array: "; 
    for (int i = 0; i < n; i++) { 
     cin >> arr[i]; 
    } 
    cout << endl; 
    cout << "Unsorted version of the array: " << endl; 
    print(arr, n); 
    cout << endl; 
    cout << "Sorted version of the array: " << endl; 
    radixSotr(arr, n); 
    print(arr, n); 

    return 0; 
} 

Jetzt versuche ich, Hollerith-Version von Radix Sort zu implementieren, wobei die Radixsort mit dem höchstwertigen Bit beginnt und breitet sich iterativ zu dem niedrigstwertigen Bit. Könntest du mir irgendwelche Ideen geben, wie ich meinen Code ändern kann, weil ich feststecke?

Answer 1

Ihre countingSort Funktion hat ein Problem:

• Sie eine Reihe von 10 Indizes zum Zählen statt int C[m] finden Sie das größte Element und erklärt verwenden soll. Ihr aktueller Code weist dem automatischen Speicher ein potenziell großes Array zu und ruft ein undefiniertes Verhalten hervor. Hier

ist eine korrigierte Version:

void countingSort(int arr[], int n, int exp) { 
    int output[n]; 
    int C[10] = { 0 }; 

    for (int i = 0; i < n; i++) 
     C[(arr[i]/exp) % 10]++; 

    for (int i = 1; i < 10; i++) 
     C[i] += C[i - 1]; 

    for (int i = n - 1; i >= 0; i--) { 
     output[--C[(arr[i]/exp) % 10]] = arr[i]; 
     C[(arr[i]/exp) % 10]--; 
    } 

    for (int i = 0; i < n; i++) 
     arr[i] = output[i]; 
} 

Beachten Sie, dass dieser Algorithmus nicht ein Array mit negativen Zahlen sortieren.

Der Hollerith-Algorithmus verwendet die niedrigstwertige Ziffer zur höchstwertigen Stelle. Es wurde erfunden, um US-Census-Daten zu sortieren, die auf Lochkarten tabelliert wurden. Dies ist ein sehr frühes Beispiel für Datenverarbeitung, die auf zurückgeht. Lochkarten verwendeten bis zum Ende des 20. Jahrhunderts 2 verschiedene Zeichencodierungsschemata mit dem Namen H-Code und T-Code. H stand für Herman Hollerith, den Erfinder dieser Sortiermaschinen, der 1929 starb. (Siehe http://ed-thelen.org/comp-hist/Knuth-Sort.html)

Für das höchstwertige Bit bis zu dem niedrigstwertigen Bit, müssen Sie Rekursion, nicht ein iteratives Verfahren wie die, die Sie haben:

• den Maximalwert finden, damit die maximale Exponent der höchstwertigen Stelle zu bekommen. das Array
• Sortierung nach der aktuellen digit
• für jede Gruppe von Elementen mit der gleichen Ziffer an der aktuellen Position:
  • wenn der Eimer leer ist oder nur ein Element ist es sortiert
  • Andernfalls rekursieren Sie den Bucket für die nächste niedrigere Ziffer mit exp/10.

Sie können dies mit jeder Base> = 2.