IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Sortier- und Suchalgorithmen



Sortier- und Suchalgorithmen

Sortier- Suchalgorithmen wie Selection Sort, Bubble Sort, Quicksort, linear Suche, binäre Suche


Autor: Christian Kutzner (Flypaper)
Datum: 02-11-2003, 11:49:59
Referenzen: keine
Schwierigkeit: Fortgeschrittene
Ansichten: 14047x
Rating: 7.4 (5x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Einleitung

Dieser Artikel beschäftigt sich mit den Sortier-Suchalgorithmen für Programmierer. Als erstes werden die einfachen Algorithmen Sortieren durch Auswahl, Sortieren durch Austausch und lineare Suche vorgestellt. Im zweiten Teil geht es dann um das binäre Suchen und das etwas schwierigere Sortierverfahren Quicksort und zum Schluss wird noch erklärt warum es diese viele verschiedenen Sortier- und Suchalgorithmen überhaupt gibt.

Sortieren durch Auswahl (Selection Sort)

Bei sortieren durch Auswahl auf englisch auch Selection Sort genannt wird immer das kleinste Element in einer Folge nach vorne gestellt. Am einfachsten ist das anhand eines Beispiels zu verstehen.

1. Beispiel:

Wir haben eine Folge wie z.B. 17, 10, 2, 12. Nun wird das kleinste Element in diesem Fall ist das die 2 nach vorne gestellt. Da dort die 17 liegt tauschen beide Elemente miteinander die Plätze und wir haben dann die Folge 2, 10, 17, 12.
Jetzt ist der erste Platz schon vergeben und es wird wieder das kleinste Element aus der Folge 10, 17, 12 rausgesucht. Wie man sieht wird die 2 nicht mehr zu der Folge dazugezählt, sie belegt schon den ersten Platz und bleibt da auch. Das kleinste Element ist nun die 10 und da sie schon an der ersten Stelle steht wird sie mit sich selber getauscht.
Nun kommt der dritte Durchlauf und es wird wieder das kleinste Element gesucht aber ohne die 2 und die 10 denn die sind schon an ihrer Stelle. Es bleiben somit 17 und 12 übrig und da die 12 kleiner als die 17 ist wird sie nach vorne gestellt. Somit tauschen die 17 und die 12 die Plätze.
Als Resultat haben wir nun die Folge 2, 10, 12, 17.

2. Beispiel:




Anhand der Grafik kann man am besten erkennen das wir immer nur die kleinste Zahl nach vorne setzt müssen und dann eins nach rechts rotieren.

Sortieren durch Austausch (Bubble Sort)

Beim sortieren durch Austausch auf englisch auch Bubble Sort genannt werden der Reihen nach wie der Name schon sagt die Elemente einer Folge vertauscht. Es werden zwei nebeneinander stehende Elemente verglichen und ist das rechte Element größer als das linke tauschen sie die Plätze.

1. Beispiel:

Wieder haben wir in unserem Beispiel die Folge 17, 10, 2, 12. Jetzt werden die Elemente 17 und 10 verglichen. Da die 10 kleiner als die 17 ist tauschen beide miteinander die Plätze. Das Resultat ist 10, 17, 2, 12, jetzt rotieren wir ein Element nach rechts und vergleichen die 17 mit der 2. Wieder ist das zweite Element kleiner als das erste und wird vertauscht. Die neue Folge ist 10, 2, 17, 12. Nachdem wir nun wieder eins nach rechts rotiert sind vergleichen wir die 17 mit der 12 und schon wieder müssen beide vertauscht werde. Nach dem ersten Durchgang haben wir nun die Folge 10, 2, 12, 17. Die sieht zwar schon anders aus als die erste ist aber auch nicht wirklich richtig sortiert. Der Grund ist das wir das gerade angewandte vertauschen wiederholen müssen. Solange bis alle rechten Elemente größer sind als die nebenstehenden linken.

2. Beispiel:




Anhand dieser Grafik können wir sehen das man für die Folge 17, 10, 02, 12 zwei Durchläufe braucht bis sie richtig sortiert ist.

Linear Suche

Die lineare Suche ist sehr einfach zu verstehen. Man hat eine Folge bei der man vom Anfang bis zum Ende durch jedes einzelne Element geht und schaut ob es das gesuchte Element ist.

Beispiel:

Wir suchen die 2 in der Folge 17, 10, 2, 12. Um dieses Element jetzt zu finden geht man einfach jedes Element von Anfang bis zum Ende durch. Wir nehmen als erstes die 17 und vergleichen sie mit dem Element 2, da sie nicht gleich sind rotieren wir ein Element nach rechts und vergleichen die 10 mit der 2. Das ist immer noch nicht das richtige Element und wir rotieren wieder ein Element nach rechts. Dort steht nun die 2 die mit dem gesuchten Element 2 verglichen wird. Da beide nun gleich sind haben wir das Element gefunden und da wir wissen, dass wir 2 mal nach rechts rotiert sind steht das gesuchte Element an der Position 2. (Man sollte beachtend das man in der Informatik beim zählen immer mit der 0 beginnt und nicht wie in der Mathematik mit der 1).

Quicksort

Quicksort ist ein etwas komplexerer Algorithmus der nicht so einfach zu verstehen ist. Das erste was man wissen sollte ist das Quicksort ein rekursiver Sortieralgorithmus ist. Das heißt der Sortieralgorithmus ruft sich selber immer wieder mit neuen Parametern auf. Quicksort funktioniert sodass es eine Folge gegeben bekommt und dort ein Mittelwert bestimmt. Nun geht man von links immer weiter zum Mittelwert und vergleicht jeweils das Element auf das gezeigt wird mit diesem Mittelwert. Ist das Element größer oder gleich wie der Mittelwert bleibt man an dieser Position. Das gleiche geschieht auch auf der rechten Seite des Mittelwertes nur mit dem Unterschied, dass das Element kleiner oder gleich des Mittelwerts sein soll. Ist das rechte Element kleiner als das Linke werden diesem miteinander vertauscht und man geht auf beide Seiten eine Position weiter bis das linke Element kleiner als das rechte Element ist. Jetzt stehen auf der linken Seite alle Elemente die kleiner oder gleich dem Mittelwert sind und rechts alle anderen Elemente. Nun wird Quicksort noch mal aufgerufen aber nur mit dem linken Teil der Folge und dann noch mal nur mit dem rechten Teil der Folge. Verständlicher wird das ganze natürlich wieder mit einem Beispiel.

1. Beispiel:

Wenn wir die Folge 2, 15, 20, 11, 4, 16, 2, 7 haben, wählen wir als erstes ein Mittelwert, dieser muss nicht in der Mitte liegen. In diesem Beispiel nehmen wir die 11 als Mittelwert. Jetzt verschieben wir alle Elemente die links stehen und größer als der Mittelwert sind nach rechts und alle Elemente die rechts stehen und kleiner als der Mittelwert sind nach links. So erhält man die Folge 2, 7, 2, 4, 11, 16, 20, 15. Nun teilen wir diese Folge in zwei einzelne Folgen, genauer gesagt in die Folge 2, 7, 2, 4 und 16, 20, 15. Diese Folgen werden dann wieder dem Quicksort übergeben (rekursiv) und dann fängt alles wieder von vorne an. Mittelwert bestimmen, links und rechts vertauschen usw. Das geht so lange bis eine Folge nur noch aus einem Element besteht. Dann werden alle einzelnen Folgen zusammengefügt zu der Folge 2, 2, 4, 7, 11, 15, 16, 20.

2. Beispiel:




Binäre Suche

Ein etwas besseres Verfahren im Gegensatz zu der linearen Suche ist die binäre Suche. Doch wenn man die binäre Suche verwendet, sollte die Folge die man durchsucht sortiert sein. Warum das so sein soll wird klar, wenn man versteht wie die binäre Suche arbeitet. Bei der binären Suche wird aus der Folge wie bei Quicksort ein Mittelwert bestimmt, ist dieser größer als das gesuchte Element kann man die rechte Seite der Folge ab dem Mittelwert wegwerfen. Nun hat man nur noch den linken Teil und es wird das gleiche gemacht wie beim ersten mal.

Beispiel:

Wir haben die Folge 2, 2, 4, 7, 11, 15, 16, 20 und suchen die 15. Der Mittelwert ist 11 und alles was darunter liegt können wir vergessen. In diesem Fall ist das 2, 2, 4, 7, 11 und es bleibt übrig die Folge 15, 16, 20. Davon der Mittelwert ist 16 und da die 16 größer als die 15 ist können wir sicher sein, dass alles was darüber liegt nicht die 15 ist die gesucht wird. Da der Rest nur noch aus einem Element besteht kann es kein anderes Element sein als das Gesuchte.

Vergleiche und Leistungen

Warum gibt es nun diese verschiedenen Algorithmen? Das liegt daran das jedes seine Vor- und Nachteile hat. Um diese Sortier- und Suchalgorithmen optimal einsetzen zu können, sollte man die Leistung bzw. Unterschiede der einzelnen Algorithmen kennen. Um dieses am besten verständlich zu machen, sollte man wissen wie viele Vergleiche die einzelnen Sortierverfahren machen.

Sortierverfahren

Wenn man sich Selection- und Bubble Sort genau anschaut dann sind die Anzahl der Vergleiche .

Aber bei Quicksort sieht das ganz anders aus, da ist die Anzahl der Vergleiche n*log(n).
Das bedeutet nun das Quicksort schneller arbeitet als Selection- und Bubbel Sort.

Trotzdem haben auch Selection- und Bubble Sort ihre Vorteile. Diese Algorithmen sind einfach zu programmieren und bei kleinen Folgen die sortiert werden fast gleichschnell wie Quicksort und da man bei Selection- und Bubbel Sort aber weniger Variabeln definiert, braucht man auch weniger Speicherplatz. Hat man aber eine Folge mit n = 1000 sieht das schon anders aus, denn bei sind das 1 Millionen Durchläufe und bei n*log(n) sind es nur 10000. Somit lohnt es sich bei großen Folgen Quicksort trotz des größeren Speicherbedarfs zu verwenden.

Suchverfahren

Bei der linearen und binären Suche sind die Unterschiede noch deutlicher. Da betrachten wir die lineare Suche als n und die binäre Suche als log(n) und schon wird einem klar, das die binäre Suche eindeutig schneller ist. Bei 1000 Elementen braucht die lineare Suche im schlechtesten Fall 1000 Durchläufe im Gegensatz zur binäre Suche mit nur 10.

Schlusswort

Man sieht, dass es viele Sortier- und Suchverfahren gibt obwohl das noch nichteinmal alle waren. Andere Algorithmen sind noch Baumsortierung, englisch Tree Sort oder sortieren durch Verschmelzung, englisch Merge Sort. Aber jeder Programmierer muss selber wissen zu was er welches Sortier- bzw. Suchverfahren einsetzt, da es wie man sieht sehr viel Unterschiede gibt.


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04508
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06243
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1144
Comments: 0