Sortieren eines Arrays von Daten ist eines der klassischen Probleme der Informatik, und so sollte es nicht überraschen, dass eine Vielzahl von Methoden für die Sortierung in Turbo C und andere Sprachen wurden konzipiert kommen . Sie reichen von ineffizienten , aber einfach zu implementieren Methoden, um viel schneller, aber komplexere Methoden . Der beste Algorithmus für eine Situation, hängt von der erwarteten Größe des Datensatzes zu sortierenden und die Bedeutung der Effizienz . Bubble Sort
Die Bubble Sort ist die einfachste und am langsamsten , Sortier- Algorithmus . Es läuft weiterhin über das Array , Vergleichen des aktuellen Elements auf das Element unmittelbar davor . Wenn diese beiden Elemente sind aus der Ordnung, schalten sie Orte . Wenn der Bubble Sort das Ende erreicht , wird überprüft, ob sich etwas geändert Orte zu sehen . Wäre dies der Fall , beginnt es wieder von vorne . Weiter geht es durch das Array Schleife , bis sie einen vollständigen Durchlauf ohne jegliche Swapping vervollständigen verwaltet . Im Durchschnitt dauert dies O ( n ²) Zeit, aber wenn die Daten bekannt, sehr knapp sortiert , mit vielleicht nur ein Element fehl am Platz , es kann in O (n) arbeiten. So ist es eine gute Methode für kleine Arrays, die nicht sortiert werden oft oder größere Arrays , die bekanntermaßen bereits sortiert werden ( oder fast so ) die meiste Zeit .
Auswahl sortieren
werden
die
Selection Art ist etwas feiner als der Bubble Sort . Der Algorithmus geht durch die ganze Reihe von Daten auf das kleinste Element zu finden. Überall dort, wo das Element ist , hat es seine Position mit dem ersten Element vertauscht , und ein Zähler stellt fest, dass das erste Element in dem Array bekannt ist, richtig sortiert werden. Es geht dann durch die gesamte Anordnung wieder , außer für das erste Element (das ist bekannt, an der richtigen Stelle ist. ) Wenn das unterste Element befindet , bewegt er ihn zu dem zweiten Ort und erhöht den Zähler um anzuzeigen, dass die ersten beiden Elemente bekannt, sortiert werden. Insgesamt arbeitet der Selection Sort in O ( n ²) Zeit , aber es hat einen Vorteil: höchstens nur n-1 Veränderungen überhaupt auftreten zu der Anordnung , da jedes Element nur bewegt wird, wenn seine Position bekannt ist. Dies macht es zu einem guten Algorithmus in einigen exotischen Situationen, in denen das Schreiben von Daten in den Speicher nimmt drastisch länger als es zu lesen.
Quicksort
Wie der Name andeutet, ist das QuickSort ist schnell. Im Durchschnitt kann sie eine Art in O ( n log n) Zeit . Aber es ist sehr viel komplexer als viele andere Programme und erfordert, dass die Entwickler ein wenig über die Daten im Array vor der Hand wissen . Zunächst wird eine "Pivot -Wert " muss gewählt werden. Dies ist der Wert, den der Entwickler glaubt, ist in der Nähe des mittleren aller Werte in dem Array . Je besser die Pivot- Wert , desto schneller die Quicksort durchführen wird. Die über dem Schwenkwertes sind zur rechten Seite bewegt wird, und die unterhalb der Schwenkachse Wert an der linken Seite bewegt wird : Dann wird die Anordnung in zwei Gruppen eingeteilt . Hoffentlich sind die beiden Seiten in der Nähe gleich in der Größe , aber sie müssen nicht genau die gleiche sein. Schließlich beginnt der quicksort Algorithmus von vorne auf jeder Seite, mit neuen Drehpunkt gewählten Werte , und diese Hälften schließlich in Viertel unterteilt. Wenn die quicksort hat das Array unterteilt , so dass jeder Abschnitt hat nur einen Wert , hat das Array sortiert.
Wie die meisten rekursive Algorithmen , kann dies schwer zu visualisieren , so dass Sie werden ermutigt, den Schritt - für Schritt sehen - Beispiel in der dritten Referenz angegeben.
