Programmierer, die von der PC- und Webentwicklung zur Codierung für mobile Geräte oder eingebettete Systeme wechseln, stellen fest, dass mehr Zeit damit verbracht wird, ihre eigenen Datenstrukturen und Algorithmen auszuwählen und zu codieren. Mit weniger Arbeitsspeicher und begrenztem Datenspeicher ist kein Platz für vorgefertigte Bibliotheken oder Frameworks. Für diejenigen, die ihre eigenen Sortierroutinen schreiben müssen, sind hier einige Überlegungen zur Auswahl der Sortierung mit niedriger Blasenbildung.
Hintergrund
Der Bubble-Sort ist ein einfacher Algorithmus, der eine Liste von Elementen im Speicher sortiert. Bei einem gegebenen Array vergleicht der Code wiederholt jedes Paar benachbarter Elemente und vertauscht sie, wenn sie nicht in Ordnung sind. Der Vorgang wiederholt sich, bis kein Tausch mehr stattfindet. Wenn es möglich wäre, das Array während des Sortiervorgangs anzuzeigen, würden die niedrigen Werte nach oben "blasen", während die großen Werte nach unten sinken würden. Hier ist der relevante Code in Visual Basic 2010:
Video des Tages
Während swap = True swap = False For i = 0 To tbl.length - 2 Wenn tbl (i) > tbl (i + 1) Dann tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End While
Wann sollte man die Bubble-Sortierung wählen?
Dieser Algorithmus hat mehrere Vorteile. Es ist einfach zu schreiben, leicht zu verstehen und benötigt nur wenige Zeilen Code. Die Daten werden an Ort und Stelle sortiert, sodass nur ein geringer Speicheraufwand entsteht. Nach dem Sortieren befinden sich die Daten im Speicher und können verarbeitet werden. Der größte Nachteil ist der Zeitaufwand für die Sortierung. Die durchschnittliche Zeit nimmt mit zunehmender Anzahl der Tabellenelemente fast exponentiell zu. Das Sortieren von zehnmal so vielen Artikeln dauert fast hundertmal so lange.
Andere Array-Sorten
Sortieralgorithmen variieren in Komplexität, Geschwindigkeit und Overhead. Die Blasensortierung ist die am wenigsten komplexe, aber auch eine der langsamsten. Andere Array-basierte Sortierungen wie die Insertion-Sortierung und die Exchange-Sortierung sind etwas schneller, benötigen aber mehr Code (siehe die Referenzen unten). Der Hauptvorteil von Array-basierten Sortierungen besteht darin, dass sie am wenigsten Code verwenden und am wenigsten Arbeitsspeicher beanspruchen. Betrachten Sie diese Sortierungen für einfache Arrays mit weniger als ein paar hundert Elementen.
Komplexe Sortieralgorithmen
Größere Datensätze erfordern komplexeren Code und mehr Speicher. Die Schnellsortierung und die Heap-Sortierung teilen und kopieren die Datensätze, um die Anzahl der Vergleiche zu optimieren. Die Schnellsortierung teilt die Liste kontinuierlich auf und setzt sie dann in sortierter Reihenfolge wieder zusammen. Die Heap-Sortierung kopiert die Daten in eine Baumstruktur und durchquert dann den Baum, um die Daten wieder in die richtige Reihenfolge zu kopieren. Beide sind schnell und effizient, benötigen aber mehr Code und viel mehr Arbeitsspeicher. Wählen Sie diese Algorithmen für große Datensätze.
