In der Informatik ist ein Sortieren-Algorithmus ein Algorithmus, der Elemente einer Liste in einer bestimmten Ordnung stellt. Die am meisten verwendeten Ordnungen sind numerische Ordnung und lexikografische Ordnung. Das effiziente Sortieren ist wichtig, für den Gebrauch anderer Algorithmen zu optimieren (wie Suche und Verflechtungsalgorithmen), die verlangen, dass sortierte Listen richtig arbeiten; es ist auch häufig für canonicalizing Daten nützlich und um menschlich-lesbare Produktion zu erzeugen. Mehr formell muss die Produktion zwei Bedingungen befriedigen:

1. Die Produktion ist in der nichtabnehmenden Ordnung (jedes Element ist nicht kleiner als das vorherige Element gemäß dem gewünschten Gesamtbezug);
2. Die Produktion ist eine Versetzung (Umstellung) des Eingangs.

Seit der Morgendämmerung der Computerwissenschaft hat das Sortieren-Problem sehr viel Forschung, vielleicht wegen der Kompliziertheit des Lösens davon effizient trotz seiner einfachen, vertrauten Behauptung angezogen. Zum Beispiel wurde Luftblase-Sorte schon in 1956 analysiert. Obwohl viele es als ein behobenes Problem betrachten, werden nützliche neue Sortieren-Algorithmen noch erfunden (zum Beispiel, Bibliothekssorte wurde zuerst 2004 veröffentlicht). Sortierende Algorithmen sind in einleitenden Informatik-Klassen überwiegend, wo der Überfluss an Algorithmen für das Problem eine sanfte Einführung in eine Vielfalt von Kernalgorithmus-Konzepten wie große O Notation zur Verfügung stellt, teilen Sie und überwinden Sie Algorithmen, Datenstrukturen, randomized Algorithmen, beste, schlechteste und durchschnittliche Fall-Analyse, Zeitraumumtausche und niedrigere Grenzen.

Klassifikation

Das Sortieren von in der Informatik verwendeten Algorithmen wird häufig klassifiziert durch:

• Rechenbetonte Kompliziertheit (schlechtestes, durchschnittliches und bestes Verhalten) Element-Vergleiche in Bezug auf die Größe der Liste (n). Für typische Sortieren-Algorithmen ist gutes Verhalten O (n loggen n), und schlechtes Verhalten ist O (n). (Sieh Große O Notation.) Ist das ideale Verhalten für eine Sorte O (n), aber das ist im durchschnittlichen Fall nicht möglich. Vergleich-basierte Sortieren-Algorithmen, die die Elemente der Liste über eine abstrakte Schlüsselvergleich-Operation bewerten, brauchen mindestens O (n loggen n) Vergleiche für die meisten Eingänge.
• Rechenbetonte Kompliziertheit des Tausches (für "im Platz" Algorithmen).
• Speichergebrauch (und Gebrauch anderer Computermittel). Insbesondere einige Sortieren-Algorithmen sind "im Platz". Ausschließlich, in der Platz-Sorte braucht nur O (1) Gedächtnis außer den Sachen, die sortieren werden; manchmal O (Klotz (n)) zusätzliches Gedächtnis wird "im Platz" betrachtet.
• Recursion. Einige Algorithmen sind entweder rekursiv oder nichtrekursiv, während andere beide (z.B, Verflechtungssorte) sein können.
• Stabilität: Stabile Sortieren-Algorithmen erhalten die Verhältnisordnung von Aufzeichnungen mit gleichen Schlüsseln (d. h., Werte) aufrecht.
• Ob sie eine Vergleich-Sorte sind. Eine Vergleich-Sorte untersucht die Daten nur durch das Vergleichen von zwei Elementen mit einem Vergleich-Maschinenbediener.
• Allgemeine Methode: Einfügung, Austausch, Auswahl, das Mischen, usw. Austauschsorten schließen Luftblase-Sorte und Schnellsortierung ein. Auswahl-Sorten schließen Mixbecher-Sorte und heapsort ein.
• Anpassungsfähigkeit: Ob der presortedness des Eingangs die Laufzeit betrifft. Wie man bekannt, sind Algorithmen, die das in Betracht ziehen, anpassungsfähig.

Stabilität

Stabile Sortieren-Algorithmen erhalten die Verhältnisordnung von Aufzeichnungen mit gleichen Schlüsseln aufrecht. Wenn alle Schlüssel dann verschieden sind, ist diese Unterscheidung nicht notwendig. Aber wenn es gleiche Schlüssel gibt, dann ist ein Sortieren-Algorithmus wenn stabil, wann auch immer es zwei Aufzeichnungen gibt (wollen wir R und S sagen) mit demselben Schlüssel, und erscheint R vorher S in der ursprünglichen Liste dann wird R immer vorher S in der sortierten Liste erscheinen.

Wenn gleiche Elemente, solcher als mit ganzen Zahlen, oder mehr allgemein, irgendwelche Daten nicht zu unterscheidend sind, wo das komplette Element der Schlüssel ist, ist Stabilität nicht ein Problem. Nehmen Sie jedoch an, dass die folgenden Paare von Zahlen durch ihren ersten Bestandteil sortiert werden sollen:

(4, 2) (3, 7) (3, 1) (5, 6)

In diesem Fall sind zwei verschiedene Ergebnisse, dasjenige möglich, das die Verhältnisordnung von Aufzeichnungen mit gleichen Schlüsseln und diejenige aufrechterhält, die nicht tut:

(3, 7) (3, 1) (4, 2) (5, 6) (Ordnung aufrechterhalten)

(3, 1) (3, 7) (4, 2) (5, 6) (Ordnung geändert)

Nicht stabile Sortieren-Algorithmen können die Verhältnisordnung von Aufzeichnungen mit gleichen Schlüsseln ändern, aber stabile Sortieren-Algorithmen tun nie so. Nicht stabile Sortieren-Algorithmen können besonders durchgeführt werden, um stabil zu sein. Eine Weise, das zu tun, ist, den Schlüsselvergleich künstlich zu erweitern, so dass Vergleiche zwischen zwei Gegenständen mit sonst gleichen Schlüsseln mit der Ordnung der Einträge in der ursprünglichen Datenordnung als ein Tie-Break entschieden werden. Das Erinnern an diese Ordnung ist jedoch häufig mit zusätzlichen rechenbetonten Kosten verbunden.

Wenn man

gestützt auf einer Vorwahl, sekundär, tertiär usw. sortiert, kann Sorte-Schlüssel durch jede Sortieren-Methode getan werden, alle Sorte-Schlüssel in Vergleichen (mit anderen Worten, mit einem einzelnen zerlegbaren Sorte-Schlüssel) in Betracht ziehend. Wenn eine Sortieren-Methode stabil ist, ist es auch zur Sorte mehrmals jedes Mal mit einem Sorte-Schlüssel möglich. In diesem Fall müssen die Schlüssel in der Größenordnung vom zunehmenden Vorrang angewandt werden.

Beispiel: das Sortieren von Paaren von Zahlen als oben durch den zweiten, dann der erste Bestandteil:

(4, 2) (3, 7) (3, 1) (5, 6) (ursprünglicher)

(3, 1) (4, 2) (5, 6) (3, 7) (nach dem Sortieren durch den zweiten Bestandteil)

(3, 1) (3, 7) (4, 2) (5, 6) (nach dem Sortieren durch den ersten Bestandteil)

Andererseits:

(3, 7) (3, 1) (4, 2) (5, 6) (nach dem Sortieren durch den ersten Bestandteil)

(3, 1) (4, 2) (5, 6) (3, 7) (nachdem, durch den zweiten Bestandteil, sortierend

die Ordnung durch den ersten Bestandteil wird gestört).

Vergleich von Algorithmen

In diesem Tisch ist n die Zahl von zu sortierenden Aufzeichnungen. Die Säulen "Durchschnittlich" und "Am schlechtesten" geben die Zeitkompliziertheit in jedem Fall unter der Annahme, dass die Länge jedes Schlüssels unveränderlich ist, und dass deshalb alle Vergleiche, Tausch und andere erforderliche Operationen in der unveränderlichen Zeit weitergehen können. "Gedächtnis" zeigt den Betrag der Hilfslagerung erforderlich darüber hinaus verwendet durch die Liste selbst unter derselben Annahme an. Das sind alle Vergleich-Sorten. Die Durchlaufzeit und das Gedächtnis von Algorithmen konnten mit verschiedenen Notationen wie theta, Omega, Groß-O, klein-o usw. gemessen werden. Das Gedächtnis und die Durchlaufzeiten ist unten für alle 5 Notationen anwendbar.

Der folgende Tisch beschreibt Sortieren-Algorithmen der ganzen Zahl und andere Sortieren-Algorithmen, die nicht Vergleich-Sorten sind. Als solcher werden sie durch einen gebundenen niedrigeren nicht beschränkt. Kompliziertheiten sind unten in Bezug auf n, die Zahl von Sachen, die, k, die Größe jedes Schlüssels und d, die durch die Durchführung verwendete Ziffer-Größe zu sortieren sind. Viele von ihnen basieren in der Annahme, dass die Schlüsselgröße groß genug ist, dass alle Einträge einzigartige Schlüsselwerte, und folglich das n, wo haben!! Gedächtnis!! Stabil!! n!! Zeichen

| - richten sich = "Zentrum" aus

|Pigeonhole-Sorte

|

|style = "background:#ddffdd" |

|style = "background:#ddffdd" ||

|style = "background:#ddffdd" | Ja

| Ja

|| - richten sich = "Zentrum" aus

|Bucket-Sorte (gleichförmige Schlüssel)

||style = "background:#ddffdd" |

|style = "background:#ffdddd" |

||style = "background:#ddffdd" | Ja

| Kein

| Nimmt Rechteckverteilung von Elementen vom Gebiet in der Reihe an.

| - richten sich = "Zentrum" aus

|Bucket-Sorte (Schlüssel der ganzen Zahl)

||style = "background:#ddffdd" ||style = "background:#ddffdd" |||style = "background:#ddffdd" | Ja| Ja

|r ist die Reihe von zu sortierenden Zahlen. Wenn r = dann Avg RT =

| - richten sich = "Zentrum" aus

|Counting-Sorte

||style = "background:#ddffdd" ||style = "background:#ddffdd" |||style = "background:#ddffdd" | Ja| Ja|r ist die Reihe von zu sortierenden Zahlen. Wenn r = dann Avg RT =| - richten sich = "Zentrum" aus

|LSD-Basis-Sorte

||style = "background:#ddffdd" ||style = "background:#ddffdd" |||style = "background:#ddffdd" | Ja| Kein|| - richten sich = "Zentrum" aus

|MSD-Basis-Sorte

||style = "background:#ddffdd" ||style = "background:#ddffdd" |||style = "background:#ddffdd" | Ja| Kein

| Stabile Version verwendet eine Außenreihe der Größe n, um alle Behälter zu halten

| - richten sich = "Zentrum" aus|MSD-Basis-Sorte||style = "background:#ddffdd" ||style = "background:#ddffdd" ||

|style = "background:#ffdddd" | Kein

| Kein

| Im Platz. k / d recursion Niveaus, 2 für die Zählung ordnen

| - richten sich = "Zentrum" aus

|Spreadsort

||style = "background:#ddffdd" ||style = "background:#ddffdd" |||style = "background:#ffdddd" | Kein| Kein

| Asymptotics basieren in der Annahme, dass n, aber der Algorithmus verlangt das nicht.

| }\

Der folgende Tisch beschreibt einige Sortieren-Algorithmen, die für den wahren Gebrauch wegen der äußerst schlechten Leistung oder einer Voraussetzung für die Spezialhardware unpraktisch sind.

Zusätzlich haben theoretische Computerwissenschaftler über andere Sortieren-Algorithmen ausführlich berichtet, die besser zur Verfügung stellen als Zeitkompliziertheit mit zusätzlichen Einschränkungen, einschließlich:

• Der Algorithmus von Han, ein deterministischer Algorithmus, um Schlüssel von einem Gebiet der begrenzten Größe zu sortieren, Zeit in Anspruch nehmend, und des Raums.
• Der Algorithmus von Thorup, ein randomized Algorithmus, um Schlüssel von einem Gebiet der begrenzten Größe zu sortieren, Zeit in Anspruch nehmend, und des Raums.
• Eine ganze Zahl, die Algorithmus sortiert, der nimmt, hat Zeit und Raum erwartet.

Algorithmen, die noch nicht oben verglichen sind, schließen ein:

• Sonderbar-gleiche Sorte
• Flashsort
• Burstsort
• Briefträger-Sorte
• Stichwortgeber-Sorte
• Samplesort
• Sortierer von Bitonic

Zusammenfassungen von populären Sortieren-Algorithmen

Luftblase-Sorte

Luftblase-Sorte ist ein einfacher Sortieren-Algorithmus. Der Algorithmus fängt am Anfang der Datei an. Es vergleicht die ersten zwei Elemente, und wenn das erste größer ist als das zweite, tauscht es sie. Es setzt fort, das für jedes Paar von angrenzenden Elementen zum Ende der Datei zu tun. Es fängt dann wieder mit den ersten zwei Elementen an, sich wiederholend, bis kein Tausch auf dem letzten Pass vorgekommen ist. Durchschnitt- und Grenzfall-Leistung dieses Algorithmus ist O (n), so wird es selten verwendet, um groß, nicht eingeordnet, Dateien zu sortieren. Luftblase-Sorte kann verwendet werden, um eine kleine Anzahl von Sachen zu sortieren (wo seine Wirkungslosigkeit nicht eine hohe Strafe ist). Luftblase-Sorte kann auch auf einer Liste effizient verwendet werden, die bereits abgesehen von einer sehr kleinen Anzahl von Elementen sortiert wird. Zum Beispiel, wenn nur ein Element nicht in der Ordnung ist, wird Luftblase-Sorte nur 2n Zeit nehmen. Wenn zwei Elemente nicht in der Ordnung sind, wird Luftblase-Sorte nur höchstens 3n Zeit nehmen...

Auswahl-Sorte

Auswahl-Sorte ist eine Vergleich-Sorte im Platz. Es hat O (n) Kompliziertheit, es ineffizient auf großen Listen machend, und leistet allgemein schlechter als die ähnliche Einfügungssorte. Auswahl-Sorte wird für seine Einfachheit bemerkt, und hat auch Leistungsvorteile gegenüber mehr komplizierten Algorithmen in bestimmten Situationen.

Der Algorithmus findet den minimalen Wert, tauscht ihn mit dem Wert in der ersten Position, und wiederholt diese Schritte für den Rest der Liste. Es tut nicht mehr als n Tausch, und ist so nützlich, wo das Tauschen sehr teuer ist.

Einfügungssorte

Einfügungssorte ist ein einfacher Sortieren-Algorithmus, der für kleine Listen und größtenteils sortierte Listen relativ effizient ist, und häufig als ein Teil von hoch entwickelteren Algorithmen verwendet wird. Es arbeitet durch die Einnahme von Elementen von der Liste eins nach dem anderen und das Einfügen von ihnen in ihre richtige Position in eine neue sortierte Liste. In der Reihe können die neue Liste und die restlichen Elemente den Raum der Reihe teilen, aber Einfügung ist teuer, verlangend, ganzen im Anschluss an durch eines zu Ende Elemente auswechselnd. Sorte von Shell ist (sieh unten) eine Variante der Einfügungssorte, die für größere Listen effizienter ist.

Sorte von Shell

Sorte von Shell wurde von Donald Shell 1959 erfunden. Es übertrifft Luftblase-Sorte und Einfügungssorte durch das Bewegen in Unordnung von Elementen mehr als eine Position auf einmal. Eine Durchführung kann als das Ordnen der Datenfolge in einer zweidimensionalen Reihe und dann dem Sortieren der Säulen der Reihe mit der Einfügungssorte beschrieben werden.

Kamm-Sorte

Kamm-Sorte ist ein relativ vereinfachter Sortieren-Algorithmus, der ursprünglich von Wlodzimierz Dobosiewicz 1980 entworfen ist. Später wurde es wieder entdeckt und von Stephen Lacey und Richard Box mit einem Artikel Byte Magazine veröffentlicht im April 1991 verbreitet. Kamm-Sorte übertrifft Luftblase-Sorte und Rivale-Algorithmen wie Schnellsortierung. Die Grundidee ist, Schildkröten oder kleine Werte in der Nähe vom Ende der Liste zu beseitigen, da in einer Luftblase sortieren, verlangsamen diese das Sortieren schrecklich. (Kaninchen, große Werte um den Anfang der Liste, werfen kein Problem in der Luftblase-Sorte auf)

Verflechtungssorte

Verflechtungssorte nutzt die Bequemlichkeit des Mischens bereits von sortierten Listen in eine neue sortierte Liste aus. Es fängt durch das Vergleichen aller zwei Elemente (d. h., 1 mit 2, dann 3 mit 4...) und das Tauschen von ihnen an, wenn das erste nach dem zweiten kommen sollte. Es verschmilzt dann jede der resultierenden Listen zwei in Listen vier, verschmilzt dann jene Listen vier, und so weiter; bis an letzten zwei Listen werden in die sortierte Endliste verschmolzen. Der Algorithmen beschrieben hier ist das erst, der gut zu sehr großen Listen klettert, weil seine Grenzfall-Laufzeit O ist (n, loggen n). Verflechtungssorte hat eine relativ neue Woge in der Beliebtheit für praktische Durchführungen gesehen, für die Standardsorte-Routine auf den Programmiersprachen Perl, Pythonschlange verwendet werden (weil timsort), und Java (auch timsort bezüglich JDK7 verwendet), unter anderen. Verflechtungssorte ist in Java mindestens seit 2000 in JDK1.3 verwendet worden.

Heapsort

Heapsort ist eine viel effizientere Version der Auswahl-Sorte. Es arbeitet auch durch die Bestimmung des größten (oder am kleinsten) Element der Liste, das Stellen davon am Ende (oder den Anfang) der Liste, dann das Weitergehen mit dem Rest der Liste, aber vollbringt diese Aufgabe effizient durch das Verwenden einer Datenstruktur genannt einen Haufen, einen speziellen Typ des binären Baums. Sobald die Datenliste in einen Haufen gemacht worden ist, wie man versichert, ist der Wurzelknoten am größten (oder am kleinsten) Element. Wenn es entfernt und am Ende der Liste gelegt wird, wird der Haufen so das größte Element umgeordnet, das Bewegungen zur Wurzel bleibt. Das Verwenden des Haufens, die Entdeckung des folgenden größten Elements nehmen O (loggen Sie n) Zeit, statt O (n) für ein geradliniges Ansehen als in der einfachen Auswahl-Sorte. Das erlaubt Heapsort, in O zu laufen (n loggen n) Zeit, und das ist auch die Grenzfall-Kompliziertheit.

Schnellsortierung

Schnellsortierung ist ein Teilen, und überwinden Sie Algorithmus, der sich auf eine Teilungsoperation verlässt: Um eine Reihe zu verteilen, hat ein Element gerufen eine Türangel wird ausgewählt. Alle Elemente, die kleiner sind als die Türangel, werden davor bewegt, und alle größeren Elemente werden danach bewegt. Das kann effizient in der geradlinigen Zeit und im Platz getan werden. Die kleineren und größeren Sublisten werden dann rekursiv sortiert. Effiziente Durchführungen der Schnellsortierung (mit dem Verteilen im Platz) sind normalerweise nicht stabile Sorten und etwas kompliziert, aber sind unter den schnellsten Sortieren-Algorithmen in der Praxis. Zusammen mit seinem bescheidenen O (loggen n), Raumgebrauch ist Schnellsortierung einer der populärsten Sortieren-Algorithmen und ist in vielen Standardprogrammierbibliotheken verfügbar. Das kompliziertste Problem in der Schnellsortierung wählt ein gutes Türangel-Element; durchweg schlechte Wahlen von Türangeln können drastisch langsamer O (n ²) Leistung hinauslaufen, wenn an jedem Schritt die Mittellinie als die Türangel dann die Algorithmus-Arbeiten in O gewählt wird (n, loggen n). Die Entdeckung der Mittellinie jedoch, ist ein O (n) Operation auf unsortierten Listen und handelt deshalb seine eigene Strafe mit dem Sortieren ex-.

Das Aufzählen der Sorte

Zählende Sorte ist anwendbar, wenn, wie man bekannt, jeder Eingang einem besonderen Satz, S von Möglichkeiten gehört. Der Algorithmus führt in O (|S + n) Zeit und O (|S) Gedächtnis, wo n die Länge des Eingangs ist. Es arbeitet durch das Schaffen einer Reihe der ganzen Zahl der Größe |S und das Verwenden des ith Behälters, um die Ereignisse des ith Mitgliedes von S im Eingang aufzuzählen. Jeder Eingang wird dann durch das Erhöhen des Werts seines entsprechenden Behälters aufgezählt. Später wird die Zählen-Reihe durch geschlungen, um alle Eingänge in der Ordnung einzuordnen. Dieser Sortieren-Algorithmus kann nicht häufig verwendet werden, weil S dafür vernünftig klein sein muss, um effizient zu sein, aber der Algorithmus ist äußerst schnell und demonstriert großes asymptotisches Verhalten als n Zunahmen. Es kann auch modifiziert werden, um stabiles Verhalten zur Verfügung zu stellen.

Eimer-Sorte

Eimer-Sorte ist ein Teilen, und überwinden Sie Sortieren-Algorithmus, der zählende Sorte durch das Verteilen einer Reihe in eine begrenzte Zahl von Eimern verallgemeinert. Jeder Eimer wird dann individuell, entweder das Verwenden eines verschiedenen Sortieren-Algorithmus, oder durch die rekursive Verwendung des Eimer-Sortieren-Algorithmus sortiert. Eine Schwankung dieser Methode hat gerufen die einzelne gepufferte Sorte der Zählung ist schneller als Schnellsortierung.

Auf Grund dessen, dass Eimer-Sorte eine begrenzte Zahl von Eimern verwenden muss, wird ihr am besten angepasst, um auf Dateien eines beschränkten Spielraums verwendet zu werden. Eimer-Sorte würde für Daten wie Sozialversicherungsnummern unpassend sein - die viel Schwankung haben.

Basis-Sorte

Basis-Sorte ist ein Algorithmus dass Sorte-Zahlen durch die Verarbeitung individueller Ziffern. n Zahlen, die aus k Ziffern bestehen, wird jeder in O sortiert (n · k) Zeit. Basis-Sorte kann Ziffern jeder Zahl bearbeiten, entweder von der kleinsten positiven Ziffer (LSD) anfangend oder vom grössten Teil der positiven Ziffer (MSD) anfangend. Der LSD-Algorithmus die ersten Sorten die Liste durch kleinste positive Ziffer, während man ihre Verhältnisordnung mit einer stabilen Sorte bewahrt. Dann sortiert es sie durch die folgende Ziffer und so weiter vom am wenigsten bedeutenden bis das bedeutendste, mit einer sortierten Liste endend. Während die LSD-Basis-Sorte den Gebrauch einer stabilen Sorte verlangt, tut der MSD Basis-Sorte-Algorithmus nicht (wenn das stabile Sortieren nicht gewünscht wird). MSD Basis-Sorte im Platz ist nicht stabil. Es ist für den Zählen-Sorte-Algorithmus üblich, innerlich durch die Basis-Sorte verwendet zu werden. Hybride-Sortieren-Annäherung, wie das Verwenden der Einfügungssorte für kleine Behälter verbessert Leistung der Basis-Sorte bedeutsam.

Vertriebssorte

Vertriebssorte bezieht sich auf jeden Sortieren-Algorithmus, wo Daten von seinem Eingang bis vielfache Zwischenstrukturen verteilt werden, die dann gesammelt und auf der Produktion gelegt werden. Sieh Eimer-Sorte, Flashsort.

Timsort

Timsort findet Läufe in den Daten, schafft Läufe mit der Einfügungssorte nötigenfalls, und verwendet dann Verflechtungssorte, um die sortierte Endliste zu schaffen. Es hat dieselbe Kompliziertheit (O (nlogn)) im Durchschnitt und den Grenzfällen, aber mit vorsortierten Daten geht es zu O (n) hinunter.

Speichergebrauch-Muster und das Index-Sortieren

Wenn die Größe der zu sortierenden Reihe Annäherungen oder das verfügbare primäre Gedächtnis überschreiten, so dass (viel langsamere) Platte oder Tausch-Raum verwendet werden müssen, wird das Speichergebrauch-Muster eines Sortieren-Algorithmus wichtig, und ein Algorithmus, der ziemlich effizient gewesen sein könnte, wenn die Reihe passend leicht im RAM unpraktisch werden kann. In diesem Drehbuch wird die Gesamtzahl von Vergleichen (relativ) weniger wichtig, und die Zahl von Zeitabteilungen des Gedächtnisses muss kopiert oder dazu getauscht werden, und von der Platte kann die Leistungseigenschaften eines Algorithmus beherrschen. So können die Zahl von Pässen und die Lokalisierung von Vergleichen wichtiger sein als die rohe Zahl von Vergleichen, da Vergleiche von nahe gelegenen Elementen zu einander mit der Systembusgeschwindigkeit geschehen (oder, mit dem Verstecken, sogar mit der Zentraleinheitsgeschwindigkeit), der, im Vergleich zur Plattengeschwindigkeit, eigentlich sofortig ist.

Zum Beispiel versorgt der populäre rekursive Schnellsortierungsalgorithmus ziemlich angemessene Leistung mit dem entsprechenden RAM, aber wegen der rekursiven Weise, wie es Teile der Reihe kopiert, wird es viel weniger praktisch, wenn die Reihe RAM nicht einfügt, weil es mehrer langsame Kopie verursachen oder Operationen zu und von der Platte bewegen kann. In diesem Drehbuch kann ein anderer Algorithmus vorzuziehend sein, selbst wenn man mehr Gesamtvergleiche verlangt.

Eine Weise, um dieses Problem zu arbeiten, das gut arbeitet, wenn Komplex registriert (solcher als in einer Verwandtschaftsdatenbank) wird durch ein relativ kleines Schlüsselfeld sortiert, soll einen Index in die Reihe schaffen und dann den Index, aber nicht die komplette Reihe sortieren. (Eine sortierte Version der kompletten Reihe kann dann mit einem Pass erzeugt werden, vom Index, aber häufig sogar lesend, der unnötig ist, weil den sortierten Index zu haben, entsprechend ist.), Weil der Index viel kleiner ist als die komplette Reihe, kann er leicht im Gedächtnis passen, wo die komplette Reihe nicht würde, effektiv das plattentauschende Problem beseitigend. Dieses Verfahren wird manchmal "Anhängsel-Sorte" genannt.

Eine andere Technik, für das Speichergröße-Problem zu überwinden, ist, zwei Algorithmen in einem Weg zu verbinden, der Vorteile der Kraft von jedem nimmt, um gesamte Leistung zu verbessern. Zum Beispiel könnte die Reihe in Klötze einer Größe unterteilt werden, die leicht im RAM passen wird (sagen Sie einige tausend Elemente), die Klötze haben das Verwenden eines effizienten Algorithmus (wie Schnellsortierung oder heapsort), und die laut mergesort verschmolzenen Ergebnisse sortiert. Das ist weniger effizient als gerade das Tun mergesort an erster Stelle, aber man verlangt weniger physischen RAM (um praktisch zu sein), als eine volle Schnellsortierung auf der ganzen Reihe.

Techniken können auch verbunden werden. Um sehr große Sätze von Daten zu sortieren, die gewaltig Systemgedächtnis sogar überschreiten, muss der Index eventuell mit einem Algorithmus sortiert werden, oder die Kombination von Algorithmen hat vorgehabt, vernünftig mit dem virtuellen Gedächtnis zu leisten, d. h., den Betrag zu reduzieren, erforderlich zu tauschen.

Ineffiziente/humorvolle Sorten

Das sind Algorithmen, die im Vergleich zu denjenigen äußerst langsam sind, die oben - Bogosort, Stichwortgeber-Sorte besprochen sind.

Siehe auch

• Das Außensortieren
• Sortierende Netze (vergleichen)
• Cocktail-Sorte
• Vergleichung
• Schwartzian gestalten um
• Das Schlurfen von Algorithmen
• Suchen Sie Algorithmen
• D. E. Knuth, Die Kunst der Computerprogrammierung, Bands 3: Das Sortieren und die Suche.

Links

• Das Sortieren von Algorithmus-Zeichentrickfilmen - Grafische Illustration dessen, wie verschiedene Algorithmen verschiedene Arten von Dateien behandeln.
• Folgende und parallele Sortieren-Algorithmen - Erklärungen und Analysen von vielen Sortieren-Algorithmen.
• Wörterbuch von Algorithmen, Datenstrukturen und Problemen - Wörterbuch von Algorithmen, Techniken, allgemeinen Funktionen und Problemen.
• Die ein bisschen Skeptische Ansicht auf dem Sortieren von Algorithmen Bespricht mehrere klassische Algorithmen und fördert Alternativen zum Schnellsortierungsalgorithmus.