Deutsch
Menü

Datenstrukturen und Algorithmen

Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?

  1. A1, 3, 8, 5, 4
  2. B3, 5, 1, 4, 8
  3. C1, 3, 4, 5, 8
Antwort und Erläuterung anzeigen

Antwort: B. 3, 5, 1, 4, 8

Das Vertauschen von 5 und 3 ergibt 3, 5, 8, 1, 4; 5 und 8 bleiben stehen; das Vertauschen von 8 und 1 ergibt 3, 5, 1, 8, 4; und das Vertauschen von 8 und 4 ergibt 3, 5, 1, 4, 8. Ein Durchlauf transportiert den Maximalwert 8 bis ans Ende, wo seine Position feststeht, und der nächste Durchlauf sortiert die übrigen vier Elemente auf dieselbe Weise. 1, 3, 8, 5, 4 ist das Array nach einem Durchlauf von Selectionsort, das das Minimum nach vorn tauscht, und 1, 3, 4, 5, 8 ist das vollständig sortierte Ergebnis.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Das Array 29, 10, 14, 37, 13 wird mit Selectionsort aufsteigend sortiert: Das Minimum des unsortierten Teils wird gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Wie sieht das Array aus, nachdem dieser Schritt zweimal ausgeführt wurde?
  2. Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?
  3. Welches Sortierverfahren hat auch im schlechtesten Fall die Komplexität O(n log n) und sortiert fast ohne zusätzlichen Speicher wie ein Arbeitsarray?
  4. Die Datensätze (Name, Punktzahl) (A, 80), (B, 70), (C, 80), (D, 70) liegen in dieser Reihenfolge vor. In welcher Reihenfolge erscheinen die Namen, wenn mit einem stabilen Sortierverfahren aufsteigend nach Punktzahl sortiert wird?
  5. In welchem typischen Fall benötigt Quicksort O(n²) Zeit?