Einführung
Das Sortieren eines Arrays ist eines der ersten ernsthaften Probleme, die im klassischen Kurs "Algorithmen und Datenstrukturen" der Informatikdisziplin untersucht wurden. In diesem Zusammenhang werden die Aufgaben des Schreibens und die entsprechenden Fragen häufig in Interviews als Praktikant oder Nachwuchsentwickler angetroffen.
Formulierung des Problems
Traditionell lohnt es sich, die Präsentation von Lösungen für das Problem mit seiner Aussage zu beginnen. Normalerweise besteht die Sortieraufgabe darin, ein Array von Ganzzahlen in aufsteigender Reihenfolge zu ordnen. Tatsächlich ist dies jedoch etwas zu einfach. Die in diesem Abschnitt beschriebenen Algorithmen können verwendet werden, um ein Array von Objekten zu ordnen, zwischen denen eine Ordnungsbeziehung hergestellt wird (dh für zwei beliebige Elemente können wir sagen: Das erste ist größer als das zweite, das zweite ist größer als das erste oder sie sind gleich). Sie können sowohl in aufsteigender als auch in absteigender Reihenfolge sortieren. Wir werden die Standardvereinfachung verwenden.
Auswahl sortieren
Eine der einfachsten Sorten ist die Auswahlsortierung.
Algorithmusbeschreibung
Das Sortieren eines Arrays nach Auswahl erfolgt wie folgt: Das Array ist in zwei Teile unterteilt. Ein Teil heißt sortiert und der andere unsortiert. Der Algorithmus geht davon aus, dass das gesamte Array durchlaufen wird, sodass die Länge des sortierten Teils der Länge des gesamten Arrays entspricht. Innerhalb jeder Iteration finden wir das Minimum im unsortierten Teil des Arrays und tauschen dieses Minimum mit dem ersten Element des unsortierten Teils des Arrays aus. Dann erhöhen wir die Länge des sortierten Teils des Arrays um eins. Ein Beispiel für eine Iteration ist unten dargestellt:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8
Implementierung
Ich schlage vor, die Implementierung dieses Algorithmus in C zu betrachten:
void choiseSortFunction(double A[], size_t N)
{
for(size_t tmp_min_index = 0; tmp_min_index < N;
tmp_min_index++) {
//
for(size_t k = tmp_min_index + 1; k < N; k++) {
if (A[k] < A[tmp_min_index]) {
double min_value = A[k];
A[k] = A[tmp_min_index];
A[tmp_min_index] = min_value;
}
}
}
}
Analyse
Ich schlage vor, diesen Algorithmus zu analysieren. Der Körper der inneren Schleife selbst nimmt O (1), dh er hängt nicht von der Größe des zu sortierenden Arrays ab. Dies bedeutet, dass zum Verständnis der Asymptotik des Algorithmus gezählt werden muss, wie oft dieser Körper ausgeführt wird. Bei der ersten Iteration der äußeren Schleife gibt es (n - 1) Iterationen der inneren Schleife. Bei der zweiten Iteration der äußeren Schleife - (n - 2) Iterationen der inneren Schleife. Wenn wir diese Argumentation weiter fortsetzen, kommen wir zu Folgendem:
Bei den Berechnungen haben wir zuerst die Eigenschaften der O-Notation und dann die Formel verwendet, um die Summe einer arithmetischen Folge zu berechnen.
Für die Bestellung ist es auch erforderlich, den zusätzlichen Speicher zu schätzen, der zum Ausführen des Algorithmus erforderlich ist. Hier ist alles viel einfacher: Wir haben nur Speicher für die Schleifenzähler und eine Variable zugewiesen - einen Puffer, der das Austauschen von 2 Array-Elementen ermöglicht. Deshalb:
Als Ergebnis der Analyse kamen wir zu dem Schluss, dass die zeitliche Komplexität des Algorithmus quadratisch von der Größe des Eingabearrays abhängt. Daher gehört diese Sortierung zur Klasse der quadratischen Sortierungen . Das Ergebnis der Analyse hängt nicht vom Inhalt des Arrays ab: Es ist bestenfalls, am schlechtesten und im Durchschnitt korrekt.
Es ist auch wichtig zu beachten, dass die Auswahlsortierung in dieser Implementierung robust ist . Ich möchte Sie daran erinnern, dass das Sortieren als stabil bezeichnet wird.wenn sich die Reihenfolge der gleichen Elemente während der Ausführung nicht ändert. Diese Eigenschaft ist für eine Bildungsaufgabe wie das Sortieren eines Arrays von Zahlen nicht sehr wichtig. Wenn wir jedoch einige komplexere Objekte mit einer festgelegten Ordnungsbeziehung sortieren, ist dies möglicherweise wichtig. Wir können ein ähnliches Beispiel betrachten, wenn wir das nächste Mal über Radix-Sortierung sprechen.
Zweiseitige Auswahlsortierung
Die Optimierung des oben implementierten Algorithmus kann von Interesse sein: Während Sie durch den unsortierten Teil des Arrays gehen, können Sie parallel zum minimalen Element nach dem Maximum suchen. Daher können Sie nach der Iteration den unsortierten Teil des Arrays nicht um eins, sondern um zwei verringern. Der Algorithmus verbessert sich nicht asymptotisch, aber dennoch kann sich die Geschwindigkeit seiner Ausführung geringfügig erhöhen, und die Anzahl der Vergleiche verdoppelt sich ebenfalls.
Rekursive Auswahlsortierung
Als Übung können Sie versuchen, einen Algorithmus nicht mithilfe einer Schleife, sondern mithilfe der Rekursion zu schreiben. In Java könnte es so aussehen:
public static int findMin(int[] array, int index){
int min = index - 1;
if(index < array.length - 1) min = findMin(array, index + 1);
if(array[index] < array[min]) min = index;
return min;
}
public static void selectionSort(int[] array){
selectionSort(array, 0);
}
public static void selectionSort(int[] array, int left){
if (left < array.length - 1) {
swap(array, left, findMin(array, left));
selectionSort(array, left+1);
}
}
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
Ergebnis
Wir haben uns eine der quadratischen Sortierungen angesehen: Auswahlsortierung, eine stabile Implementierung unter Verwendung einer Schleife, Rekursion, Diskussion der Algorithmusoptimierung durch bidirektionale Reduktion des unsortierten Teils des Arrays. Das Sortieren ist rein lehrreich und hat in der Praxis keine breite Anwendung gefunden.
Wenn Sie mehr über den Kurs erfahren möchten, lade ich alle zu einem kostenlosen Webinar ein, das am 10. Juli stattfinden wird .