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

Sortieralgorithmus Mischsort

Mitglied: 73011

73011 (Level 1)

04.01.2009, aktualisiert 05.01.2009, 9118 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: https://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
Sicherheit

MikroTik-Router patchen, Schwachstelle wird ausgenutzt

Information von kgborn vor 7 StundenSicherheit

Am 23. April 2018 wurde von Mikrotik ein Security Advisory herausgegeben, welches auf eine Schwachstelle im RouterOS hinwies. Mikrotik ...

Windows 10

Microcode-Updates KB4090007, KB4091663, KB4091664, KB4091666 für Windows 10

Information von kgborn vor 13 StundenWindows 101 Kommentar

Kurze Information für Administratoren von Windows 10-Systemen, die mit neueren Intel CPUs laufen. Microsoft hat zum 23. April 2018 ...

iOS
Updates für Iphone und Co
Information von sabines vor 17 StundeniOS

Gestern abend ist iOS 11.3.1 erschienen, ein kleineres Update, dass einige Lücken schließt und "Lahmlegen" nach einem Display Tausch ...

Windows 7

Windows 7 - Server 2008 R2: Exploit für Total Meltdown verfügbar

Information von kgborn vor 2 TagenWindows 7

Kleine Information für Administratoren, die für die Updates von Windows 7 SP1 und Windows Server 2008 R2 SP1 verantwortlich ...

Heiß diskutierte Inhalte
Batch & Shell
Powershell: Im AD nach Rechnern mit bestimmten IP-Adressen suchen
gelöst Frage von Raven42Batch & Shell36 Kommentare

Hallo zusammen, ich suche nach einer Möglichkeit nach Computern im AD zu suchen , deren IP-Adresse mit 10.11.12. beginnt. ...

C und C++
Frage1 C Programmierung-Makefile Frage2 PHP-Programmierung HTTP-Fehler 404
Frage von KatalinaC und C++34 Kommentare

Hallo, ich habe 2 Fragen, die nichts miteinander zu tun haben aber mit denen ich mich gerade beschäftige: 1. ...

LAN, WAN, Wireless
Watchguard T15 VPN Einrichtung
gelöst Frage von thomasjayLAN, WAN, Wireless25 Kommentare

Hallo zusammen, wir möchten gerne über unsere Watchguard T15 einen VPN-Tunnel (Mobile VPN with IPSec) einrichten! Als Client nutzen ...

Windows Server
Alten DC entfernen
Frage von smartinoWindows Server24 Kommentare

Hallo zusammen, ich habe hier eine Umgebung übernommen und erstmal einen DCDIAG gemacht. Dabei fällt auf, daß eine ganze ...