Top-Themen

Aktuelle Themen (A bis Z)

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit

Frage Entwicklung Bibliotheken & Toolkits

Sortieralgorithmus Mischsort

Mitglied: 73011

73011 (Level 1)

04.01.2009, aktualisiert 05.01.2009, 9060 Aufrufe, 1 Kommentar

schnelle Datensortierung

Hallo zusammen! Bitsqueezer hat um eine Erklärung gebeten für den Sortieralgorithmus Mischsort: Hier ist sie:
Funktionsprinzip des Sortieralgorithmus Mischsort (Version 04-01-09):

Die zu sortierenden Daten stelle man sich als gemischtes Kartenspiel vor, zur Vereinfachung zunächst 32 Stück.
Im ersten Schritt werden diese Karten zu 16 geordneten 2-er Stapeln ausgelegt, jeweils die kleinere auf die größere. Dann werden nacheinander daraus 8: 4-er Stapel, dann 4: 8-er Stapel, 2: 16-er Stapel und am Ende 1: 32-Stapel zusammengemischt,also stets zwei nebeneinanderliegende Stapel zu einem vereinigt. Die Ordnung wird dadurch hergestellt, dass jeweils die kleinere Karte genommen wird, die auf einem der beiden Teilstapel oben liegt. Da diese aus dem vorangegangenen Schritt geordnet vorliegen, braucht dabei stets nur die oberste Karte betrachtet werden und nicht der ganze Stapel. Damit entfallen sehr viele If-Abfragen, was die Zeitersparnis gegenüber anderen Sortiermethoden wie z.B. „bubblesort" begründet.

In der Praxis der Datensortierung ergeben sich zwei -komlizierende- Unterschiede zum einfachen Bild von oben:
1.) Beim Karteneinsammeln nimmt man den neu entstehenden Stapel in die Hand, beim Datensortieren verbleibt er im Datenstapel: Das „Mischen" ist ein Verwalten von Nummern im Datenarray. Von den zwei zu mischenden „Teilstapeln" wird der „obere" in ein Hilfsarray kopiert, die alten Adressen sind zum Einsortieren der Daten frei. Wenn Daten vom „unteren Teilstapel" nach oben sortiert werden, machen sie unten weitere Plätze frei, sodass der freie Bereich stets genauso gross ist wie die Anzahl der einzusortierenden Daten.
2.) Die Datenarrays haben in der Praxis kaum je die Länge von glatten 2-er-Potenzen wie 4,8,16,32 usw. Daher geht das Zusammenmischen meist nicht glatt auf: Es bleiben „Reststapel" mit „krummen Stapelhöhen" übrig, die jeweils mitzuverwalten sind. Diese Reststapel spielen aber nur dann eine Rolle, wenn beim Durchlaufen der äußeren Programmschleife ein neu entstehender Reststapel (die Zahl der regulären Stapel war dann ungerade) auf einen schon von früher vorhandenen trifft: diese beiden Reststapel müssen dann zusammengemischt werden. Ist nur ein einzelner Reststapel vorhanden, so verbleibt er als „alter" Reststapel solange am Ende des Arrays, bis er auf einen „neuen" trifft, spätestens nach dem letzten Schleifendurchlauf, wenn das -fast- fertig gemischte Array diesen „neuen" Reststapel bildet.

Rechenzeitvergleich:
Den experimentellen Tests lag jeweils ein Datenarray aus ganzzahligen Zufallszahlen zugrunde, verglichen wurden Sortierzeiten für dieselben Arrays, für jede Feldlänge mehrfach, um statistische Ausreißer bei den Verteilungen zu minimieren.
Bei der als „Bubblesort" bekannten Methode ist die Rechenzeit t = k*x(x-1) , wenn x die Anzahl der zu sortierenden Daten ist, dies ergibt sich aus der Zahl der zu durchlaufenden If- Abfragen und wurde gut bestätigt.
In einer vorangegangenen Version von Mischsort (dabei wurden die Teilstapel ohne einen Hilfsarray zusammensortiert, wozu vielfach Teilstapel verschoben wurden) ergab sich ein gleicher funktionaler Zusammenhang allerdings bei nur ca. 22% Zeitaufwand.
Durch Einführen des Hilfsarrays veränderte sich die Zeitabhängigkeit völlig: t ist direkt proportional zu x, was die Rechenzeit vor allem bei großen Datenmengen radikal verkürzt.

Graphische Auswertung:
92a848399cf622ec688c6440c303234c-testauswertung - Klicke auf das Bild, um es zu vergrößern


Hier der Quelltext des Sortieralgorithmus, bestehend aus zwei Funktionen:
3282dafd121a5fad36f54751c207abdf-struktogramm_1 - Klicke auf das Bild, um es zu vergrößern
void Mixer(double dat1[65535],int ugos, int ugus,int hos, int hus)
/* */
/* Sortierfunktion: mischt zwei geordnete Datenstapel zu einem neuen */
/* geordneten Datenstapel. */
/* enthält die einzige Sortieranweisung: zum Abwärtssortieren ist die */
/* Bedingung "dat1(ugus)<dat1(ugos)"in der einzigen if-Bedingung zu er- */
/* setzen durch "dat1(ugus)>dat1(ugos)" */
/* */
{
double tv[32768]; int utvz = 1;
for(int i=1;i<=hos;i++){tv[i]=dat1[ugos+i-1];} /* kopiert den oberen Teilstapel */
while (hus*hos>0) /* Abbruch, wenn ein Teildatenstapel leer ist */
{
if(dat1[ugus]<tv[utvz])
{
dat1[ugos]=dat1[ugus]; /* oberes Element vom unteren Stapel einsortieren */
hus--;ugus++; /* Stapelhöhe- und -grenze (unt.Stapel)heraufsetzen */
}
else
{
dat1[ugos]=tv[utvz]; /* oberes Element vom Kopierstapel einsortieren */
hos--;utvz++; /* Stapelhöhe- und -grenze (Kop.Stapel)heraufsetzen */
}
ugos++;
}
while(hos>0) /* Reste vom oberen Stapel einkopieren */
{
dat1[ugos]=tv[utvz]; /* oberes Element vom Kopierstapel einsortieren */
hos--;utvz++;ugos++; /* Stapelhöhe- und -grenze (Kop.Stapel)heraufsetzen */
}

return;
}


0ef5d7788e88664f6055448fdb6168da-struktogramm_2 - Klicke auf das Bild, um es zu vergrößern
void Mixsortierer(double dat1[65535],int ianz)

/* */
/* Erstellt, verwaltet und zählt Datenstapel und */
/* übergibt sie an die eigentliche Sortierfunktion "Mixer". */
/* Übergibt das Datenfeld dat1 geordnet ans Hauptprogramm zurück. */
/* */
{short zremi; int hst=1; int rstha=0; int rsthn; int stz=ianz; int ugost;
while (hst<ianz) /* zählt die Teilstapelhöhen */
{
rsthn=hst*(stz%2); /* prüft, ob ein neuer Reststapel entsteht */
zremi=0;if(0<rstha*rsthn){zremi=1;} /* prüft, ob ein alter und ein neuer Reststapel vorhanden ist */
ugost = 1;
while (ugost <1+ianz-hst-rsthn-rstha) /* verwaltet die Anfangsadresse des oberen Stapels */
{
Mixer(dat1,ugost,ugost+hst,hst,hst); /* übergibt die Anfangsadressen beider Stapel und die gemeinsame Stapelhöhe */
ugost+=(2*hst);
}
if(zremi == 1) /* wenn alter und neuer Reststapel vorhanden sind, werden diese gemischt */
{
Mixer(dat1,ugost,ugost+rsthn,rsthn,rstha); /* übergibt die Anfangsadressen beider Reststapel und die unterschiedlichen Stapelhöhen*/
}
rstha+=rsthn; /* Aktualisiert die Höhe des "alten" = jetzt einzigen Reststapels */
stz/=2;hst*=2; /* Aktualisiert Zahl und Höhe der normalen Stapel */
}
return;
}

so on, karhu612
Mitglied: miniversum
04.01.2009 um 18:58 Uhr
Für sourcecode gibts die Codetags.
< code >
< / code >
Weiteres findest du hier: http://www.administrator.de/helpsystem/detail.php?idx=20
Bitte warten ..
Ähnliche Inhalte
Batch & Shell
MP3 Sortieralgorithmus
Frage von SaranaDimicarusBatch & Shell9 Kommentare

Hallo Community, ich versuche mir per Power-Shell einen einfachen Sortieralgorithmus für meine MP3 Downloads zu erstellen. (Falls die Frage ...

Neue Wissensbeiträge
Tipps & Tricks

Solutio Charly Updater Fehlermeldung: Das Abgleichen der Dateien in -Pfad- mit dem Datenobject ist fehlgeschlagen

Tipp von StefanKittel vor 16 StundenTipps & Tricks

Hallo, hier einmal als Tipp für alle unter Euch die mit der Zahnarztabrechnungssoftware Charly von Solutio zu tun haben. ...

Sicherheit

Meltdown und Spectre: Wir brauchen eine "Abwrackprämie", die die CPU-Hersteller bezahlen

Information von Frank vor 17 StundenSicherheit11 Kommentare

Zum aktuellen Thema Meltdown und Spectre: Ich wünsche mir von den CPU-Herstellern wie Intel, AMD oder ARM eine Art ...

Sicherheit

Meltdown und Spectre: Realitätscheck

Information von Frank vor 18 StundenSicherheit9 Kommentare

Die unangenehme Realität Der Prozessorfehler mit seinen Varianten Meltdown und Spectre ist seit Juni 2017 bekannt. Trotzdem sind immer ...

Sicherheit

Meltdown und Spectre: Die machen uns alle was vor

Information von Frank vor 18 StundenSicherheit12 Kommentare

Aktuell sieht es in den Medien so aus, als hätten die Hersteller wie Intel, Microsoft und Co den aktuellen ...

Heiß diskutierte Inhalte
Windows 10
Netbook erkennt Soundkarte nicht - keinerlei Info zum Hersteller und Modell vom Netbook und Hardware bekannt
Frage von 92943Windows 1031 Kommentare

Guten Tag, meine Schwester reist in einigen Wochen für ein paar Monate ins Ausland und hat sich dafür ein ...

Batch & Shell
Anmeldevorgang für Informatikraum (Schule) unter Windows
gelöst Frage von IngenieursBatch & Shell29 Kommentare

Hey zusammen, ich werde in naher Zukunft den Informatik Raum meiner jetzigen Schule von dem aktuellen Betreiber übernehmen (Vertrag ...

Netzwerkgrundlagen
Welches Modem für VDSL 50000 der T-Com
gelöst Frage von Windows10GegnerNetzwerkgrundlagen21 Kommentare

Hallo, ein Kollege von mir will sich VDSL50000 von der T-Com holen, um daran einen Server zu betreiben. Ich ...

Batch & Shell
AD-Abfrage in Batchdatei und Ergebnis als Variable verarbeiten
gelöst Frage von Winfried-HHBatch & Shell19 Kommentare

Hallo in die Runde! Ich habe eine Ergänzungsfrage zu einem alten Thread von mir. Ausgangslage ist die Batchdatei, die ...