radixsort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:03 Mi 04.06.2008 | | Autor: | gianna |
| Aufgabe | Wir wollen Null-terminierte C-Strings variabler Lange mit Hilfe von Varianten von Radix-Sort
sortieren. Dazu sollen die beiden folgenden Varianten implementiert werden:
(i) (Most-signi cant-digit)-Radix-Sort.
Diese Variante von Radix-Sort sortiert in jedem Schritt die Strings nach dem d-ten Zeichen,
arbeitet dabei aber im Unterschied zu der in der Vorlesung behandelten Variante
von links nach rechts, beginnt also mit dem 0-ten Zeichen. Dadurch wird es notwendig,
die entstehenden Gruppen (also alle Strings, die an der d-ten Stelle das gleiche Zeichen
haben) jeweils getrennt nach dem (d + 1)-ten Zeichen weiterzusortieren; es genugt hier
nicht, jeweils ein stabiles Sortierverfahren auf die komplette Eingabefolge anzuwenden.
Das Sortieren nach dem d-ten Zeichen erfolgt jeweils mit Hilfe von Counting-Sort.
Implementiere ein Programm, das als Parameter die Anzahl n der Strings und den zu benutzenden
Algorithmus einliest, n zufallige Strings variabler Lange (bis zu einer vorgegebenen
Maximallange) uber dem Alphabet 'A',. . . ,'Z' erzeugt, und schlielich den gewahlten Sortieralgorithmus
aufruft. Teste nach dem Sortieren, ob die Folge auch wirklich sortiert ist und gib das
Ergebnis des Tests aus. Gib auerdem die Laufzeit fur das Sortieren aus.
Fur die oben beschriebenen Algorithmen zum Sortieren von Strings ist es wichtig, dass fur kleine
Eingabefolgen ein einfaches Sortierverfahren benutzt wird. Verwende dazu bei beiden Varianten
Insertion-Sort, wenn die Anzahl der zu sortierenden Strings unter einem (gut gewahlten)
Schwellwert M liegt. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
also, in der vorlesung haben wir uns mit der LSD variante von radixsort und mit zahlen beschäftigt, mein problem liegt bei der aufgabe schon darin,dass ich mir nicht vorstellen kann, wie der algorithmus arbeitet,wenn man nach dem ersten buchstaben sortiert hat und dann den 2. vergleicht,theoretisch würde man ja separat alle a -wörter, b-wörter usw untersuchen und am ende alles anfügen.. ah ich verzweifle hieran, so sieht man quellcode für countingsort aus, wobei ich noch gar nicht,die wörter richtig abteilen konnte,die ja durch [mm] \0 [/mm] determiniert sind..
vlt hat jmd nen besseren ansatz zu der aufgabe
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <math.h>
using namespace std;
void countingsort( char *A[], int n, int d)
{
int k= 26;
int C[k];
int i;
char *D[27];
int laenge=n;
for (i=1;i<k;i++)
{
C[i]=0;
}
char B[27];
char j;
int a=1;
B[0]='/0';
for(j='a';j<='z';j++){
B[a]=j;
a++;
}
int b, c;
for(b=0;b<k;b++){
for(c=0;c<k;c++){
if(A[b][d]=B[c]){
C[c]++;
}
}
}
for(i=1;i<k;i++){
C[i]=C[i]+C[i-1];
}
for(i=laenge-1;i>=0;i--){
for(b=0;b<k;b++){
if(A[i][d]=B[b]){
D[b]=A[i];
C[b]=C[b]-1;
}
}
}
for(int j = 0; j<laenge; j++)
{
A[j] = D[j];
}
}
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Fr 06.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
