Implementieren von Sortier- und/oder Suchalgorithmen - wo und warum

Question

Von Zeit zu Zeit stoße ich auf manuell implementierte Sortier- und/oder Suchalgorithmen, anstatt in Sprache implementierte Algorithmen zu verwenden. Der meiste Quellcode, den ich untersucht habe, ist in Java, C# oder PHP geschrieben - aber ich denke, dieses Phänomen ist sprachunabhängig.

In Bezug auf regelmäßige Datenstrukturen wie Listen; Warum und wo implementieren Sie Ihren eigenen Algorithmus? Ideologische Gründe? Speicher effizienter? Kann die Idee, integrierte Funktionen zu verwenden, nicht ertragen? Java verwendet vorzugsweise mergesort (in Collections.sort()), was einige Gemeinkosten hat, wenn Sie es mit Quicksort als Beispiel vergleichen. Wenn Sie einen Favoriten haben, den Sie regelmäßig für allgemeine Aufgaben verwenden, können Sie ihn gerne in Ihrer bevorzugten Sprache einreichen!

Answer 1

In C++ können Sie einen Container mit einem Array innerhalb haben, das nur von Methoden des Containers durchsucht wird. Sie können eine Bibliotheksimplementierung verwenden, aber dann müssen Sie eine Komparatorklasse bereitstellen, und das ist die gleiche Menge an Code wie beim Schreiben einer for() -Schleife. Warum eine neue Entität (Vergleichsklasse) für einen solchen Fall produzieren?

Answer 2

• Nicht jeder Sortieralgorithmus wird von der Standardbibliothek implementiert.
• Nicht unterstützt jede Sprache generische Datentypen/Container
• Manchmal müssen Sie je nach Datengröße zwischen Sortieralgorithmen wechseln
• Tweaking den Algorithmus für einen bestimmten Satz von Eingangs ist einfacher
• Um die Prozessorgeschwindigkeit
messen
• wiss
• Just for fun

Dies sind nur einige der Gründe, ...

Answer 3

Bogosort:

while (!is_sorted(array)) { 
    randomly_shuffle(array); 
} 

Erwartete Laufzeit: (! N) O

:)

Answer 4

in Sprachimplementierungen Errichtet werden in der Regel schneller sein, aber nur, wenn Sie sortieren/Standard suchen. Sobald Sie etwas Ungewöhnliches tun, sei es die Art und Weise, wie der Schlüssel interpretiert wird, mit mehreren Zeigern umgehen, sich in eine andere Umgebung einklinken und so weiter, können Sie die Leistung optimieren, indem Sie die grundlegenden Routinen an Ihre genauen Anforderungen anpassen.

Zum Beispiel musste ich drei große (riesige) Datensätze auf dem gleichen Schlüssel sortiert halten, also musste ich zurück zur Quelle gehen und den C-Quick-Sortiercode ändern, um Elemente auf drei verschiedenen Datenfeldern zu verschieben.