005
09.10.2005, 23:36 Uhr
imhotep
followed the white rabbit
|
Es gibt noch eine paar Optimierungsmöglichkeiten für Bubblesort. Damit das nicht unnötig lauen muss, da es eh schon eine der langsamsten Methode ist.
| C++: |
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <iomanip.h>
//-----------------------------------------------------------------------
int main()
{
int tab[10], i=0 , j=0 , hilfsfeld;
int fertig; // wird gebraucht um zuerkennen, das eine Vertauschung ablief
for (i=0; i<10; i++) tab[i] = rand();
j = 9; // zu sortierenden Bereich
do {
fertig = 1;
for (i=0; i < j ; i++)
{
if (tab[i+1] < tab[i])
{
fertig = 0; // es musste was getauscht werden
hilfsfeld = tab[i];
tab[i] = tab[i+1];
tab[i+1] = hilfsfeld;
}
}
j--; // Liste um eins verkürzen.
} while (fertig == 0); // wenn nichts mehr sortiert wurde ist Schluss
getch();
clrscr();
for (i=0; i<10; i++) cout<<tab[i];
getch();
return 0;
}
|
Die Optimierung umfasst 2 Gedanken:
1. Wenn man durch die Liste durch ist und nichts unsortiertes gefunden hat, ist die Liste sortiert.
2. Nach jedem Durchlauf wird die Liste, die zu sortieren ist um 1 kleiner, weil das grösste Element immer ans Ende getauscht wird. |
