Blog durchsuchen

Profil

Marcus Frenkel hat Informatik an der HTWK Leipzig studiert und versucht sich derzeit an wissenschaftlicher Arbeit und einer Promotion im gleichen Fach. Außerhalb der digitalen Welt musiziert er gern, ist begeisterter Sportler und Leser von Scheibenwelt-Romanen.

06.10.11 · 22:22 Uhr

Algorithmen - Bubblesort und Selectionsort

Kategorie: Technik · Kommentare: 22

In den letzten Artikeln habe ich versucht, das grundlegende Vorgehen beim Programmieren darzulegen - einerseits natürlich, um die Idee des Programmierens selbst zu erläutern, andererseits aber natürlich auch, um die Grundlagen für die Erklärung der eigentlichen Aufgabe der Informatik zu schaffen: der Problemlösung. Der durchschnittliche Informatiker hat im Arbeitsalltag nämlich in der Regel relativ wenig mit Computern an sich zu tun (abgesehen davon, dass er an ihnen programmiert); viel öfter ist er damit beschäftigt, für ein gegebenes Problem nach einer Lösung zu suchen. Ein Problem kann hier alles mögliche sein; von der Lösung einer einfachen Gleichung über die Suche nach dem kürzesten Pfad auf einer Landkarte bis hin zu komplexen Simulationen ist alles denkbar. Die Lösung ist natürlich immer vom Problem abhängig, wobei typischerweise für ein Problem viele verschiedene Lösungen mit jeweils ganz eigenen Vor- und Nachteilen existieren. Ein häufig anzutreffendes, bereits vielfach gelöstes und daher teilweise trivialisiertes Problem ist die Sortierung einer Menge von Daten. Was ein Mensch relativ intuitiv machen kann, ist für den Computer harte Arbeit (der Mensch wird dem Computer beim Sortieren trotzdem immer unterlegen bleiben) und wird von den sogenannten Sortieralgorithmen erledigt. Und um zwei deren einfachste Vertreter soll es heute gehen (übrigens werden Sortieralgorithmen üblicherweise auf der Grundlage von Feldern natürlicher oder ganzer Zahlen erklärt und an diese Konvention möchte ich mich hier auch halten).

Thilo drüben im Mathlog hat bereits vor einiger Zeit ein wunderbares Video zum Bubblesort-Algorithmus gepostet. Für alle, die das Video noch einmal sehen wollen oder noch nicht gesehen haben: hier ist es.

Der Algorithmus folgt einem einfachen Schema, bei welchem von links nach rechts durch das zu sortierende Feld durchgehend immer zwei benachbarte Elemente miteinander verglichen werden; ist das linke Element größer als das rechte, so werden beide Elemente ausgetauscht und somit die größeren Elemente nach rechts verschoben. Ist man so einmal durch das Feld durchgewandert, beginnt man von vorne - so lange, bis alle Elemente sortiert sind. Der Algorithmus wird Bubblesort genannt, da die einzelnen Elemente wie Blasen nach oben (im Feld nach rechts) aufsteigen; zuerst landet das größte Element ganz rechts, danach folgt das zweitgrößte Element und so weiter. Dieses paarweise Vergleichen und Vertauschen ist im Video oben gut zu sehen. Übrigens muss nur beim ersten Durchlauf nur bis ganz nach rechts gesucht werden - danach ist garantiert, dass sich das größte Element an dieser Stelle befindet. Nach dem zweiten Durchlauf ist dementsprechend das zweitgrößte Element garantiert an der zweiten Stelle von rechts und so weiter (auch das sieht man im Video gut, wenn sich die "fertigen" Tänzer am Ende eines Durchlaufes umdrehen). Möchte man den Algorithmus in einer Programmiersprache umsetzen, so wird er ungefähr so aussehen (der Code sollte jetzt eigentlich jedem verständlich sein; wichtig: Felder sind hier 0-indiziert, der erste Index ist also "0" und nicht "1", der größte Index bei einer Feldlänge von "n" demzufolge "n-1" und nicht "n"; mit "swap" wird die Funktion bezeichnet, die 2 Elemente im Feld austauscht):

(1) Bubblesort: a ∈ Nⁿ → Nⁿ:
(2) for i from n-1 to 1:
(3) for j from 1 to i:
(4) if a[j-1] > a[j]:
(5) swap( a[j-1], a[j] )
(6) return a

Wer den Algorithmus jetzt noch nicht ganz verstanden hat, der vergleicht am besten den Code mit obigem Video; dann sollte es (hoffentlich) klar werden. Bubblesort ist ein relativ ineffizienter Sortieralgorithmus, da er relativ viele Vergleiche benötigt, um ein gegebenes Feld zu sortieren; es gibt weitaus effizientere Algorithmen für die Lösung dieses Problems, aber die werde ich ein andermal erläutern.

An dieser Stelle möchte ich einen anderen Sortieralgorithmus vorstellen, den sogenannten Selectionsort-Algorithmus. Der Algorithmus ist ähnlich ineffizient wie Bubblesort, entspricht aber im Vorgehen eher dem intuitiven, "menschlichen" Ansatz - daher hier die Erwähnung. Zur Einstimmung aber erst einmal noch ein Video (bei welchem der Macher des Videos scheinbar ob der Länge des Tanzes die Geduld verloren und nach kurzer Zeit die Fast-Forward-Funktion aktiviert hat):

Ein Mensch sortiert eine Menge von Objekten oft derart, dass er zuerst das kleinste Element aus der Menge heraussucht, danach das zweitkleinste, dann das drittkleinste und so weiter, bis er alle Elemente der Reihenfolge nach sortiert hat. Selectionsort folgt genau diesem Schema (wie auch gut im Video zu erkennen): das zu sortierende Feld wird von links nach rechts durchlaufen, wobei das kleinste Element herausgesucht wird; dieses wird im Anschluss ganz nach links sortiert; danach wird ab der zweiten Stelle im Feld nach dem zweitkleinsten Element gesucht und so weiter. Wenn wir das ganze als Code aufschreiben, erhalten wir folgenden Algorithmus:

(1) Selectionsort: a ∈ Nⁿ → Nⁿ:
(2) min ∈ N
(3) for i from 0 to n-1:
(4) min ← i
(5) for j from i+1 to n-1:
(6) if a[j] < a[min]:
(7) min ← j
(8) swap( a[i], a[min] )
(9) return a

Zum Codeverständnis am besten noch einmal Video und Code parallel anschauen; aber Achtung: der Tanz unterscheidet sich in einem kleinen Detail vom hier notierten Algorithmus (wer den Unterschied findet, kann ihn gerne in den Kommentaren erläutern).

Damit haben wir zwei der grundlegendsten Sortieralgorithmen kennengelernt. Sie sind nicht aufregend und nicht sonderlich effizient, aber aufgrund ihrer Einfachheit beliebte Kandidaten zur Erklärung von Programmierkonzepten. In zukünftigen Artikeln wird der Schwierigkeitsgrad aber etwas anheben und wir werden etwas komplexere Algorithmen anschauen; im Zuge dieser Artikel werden wir auch Begriffe wie Komplexität, Landau-Notation, stabiles Sortieren und in-place-Algorithmen kennenlernen - man darf also gespannt sein.

Übrigens: im Tanz zum Bubblesort-Algorithmus ist ein kleiner Fehler enthalten; wer ihn findet, gebe doch bitte in den Kommentaren über seine Erkenntnis Bescheid (ich möchte die Profi-Informatiker unter meinen Lesern bitten, sich mit der Auflösung wenigstens ein paar Tage zurückzuhalten, damit auch der "Nachwuchs" eine Chance bekommt).

Und vielleicht noch eine kleine Diskussionsaufgabe für die Kommentare: in welche Themen-Kategorie sollen nach Meinung der Leser die Artikel zum Thema Algorithmen und Datenstrukturen eingeordnet werden - "Technik" oder "Naturwissenschaften"? Oder doch ganz woanders hin?

Autor: Marcus Frenkel· 22 Kommentare· Permalink· Trackback-URL

Tags: Algorithmus· Bubblesort· Selectionsort· Sortieralgorithmus

Kommentare (22)

roghurt· 06.10.11 · 23:34 Uhr

Technik klingt ganz vernünftig.
Der Artikel wird allerdings nicht im kurzen Blogticker (letzten 3 Artikel) angezeigt, wodurch bei meiner Lesegewohnheit die Chance ihn zu übersehen groß ist.

Rob· 07.10.11 · 00:12 Uhr

Da du in deinen Artikeln sehr schön auf die zugrunde liegenden Konzepte eingehst, fände ich Naturwissenschaft eigentlich passender. Ich nehme mal stark an dass die Nähe zur Mathematik in den folgenden Artikeln noch deutlicher wird (besonders beim Komplexitätsbegriff kann ich mir das gar nicht anders vorstellen).

rolak· 07.10.11 · 05:45 Uhr

'Technik' steht imho von den wenigen verfügbaren Kategorien als einzige nicht in direktem Widerspruch zur IT.
*zurückhalt* ;-)

Stefan W.· 07.10.11 · 06:52 Uhr

Wieso sprichst Du von

sogenannten Sortieralgorithmen

? Sortieren sie nicht wirklich, oder sind es nicht wirklich Algorithmen?

MartinB· 07.10.11 · 07:46 Uhr

Algorithmen sind meiner Ansicht nach angewandte Mathematik, Mathematik ist keine Naturwissenschaft. Da es aber Wissenschaft ist, bleibt wohl nur die Geisteswissenschaft.
(ganz fies grins)

Marcus Frenkel· 07.10.11 · 10:08 Uhr

@Stefan W.
Das Wort "sogenannte" kann man nicht nur mit Ironischem Unterton benutzen, sondern hat tatsächlich die Bedeutung, dass man damit die Benennung einer Sache ankündigt. Und in dem Sinne ist es hier benutzt. ;)

@MartinB
Weiche, oh Infamer!

Ketzu· 07.10.11 · 12:22 Uhr

Physik ist meiner Meinung nach angewandte Mathematik, Mathematik ist keine Naturwissenschaft. Da es aber Wissenschaft ist, bleibt wohl nur die Geisteswissenschaft. ]:>

Ketzu· 07.10.11 · 12:25 Uhr

Uh... diskussionsaufgabe übergangen, weil Klausurtext nicht gelesen: Ich würde sie unter Naturwissenschaft einordnen. Die Informatik als Naturwissenschaft, der Computer als Technikprodukt. Verbesserung von Algorithmen als Wissenschaftliche Erkenntnis, das neue iPhone als entwicklung der Technik. :)

Dr. Webbaer· 07.10.11 · 14:58 Uhr

I.p. angewandte Mathematik wäre man bei der IT (informatik), der Philosophie und der Physiklehre nicht schlecht bedient...
Zuvor verdient sich die Informatik idT soz. im luftleeren Raum.

Dr. Webbaer· 07.10.11 · 15:08 Uhr

Das Wort "sogenannte" kann man nicht nur mit Ironischem Unterton benutzen, sondern hat tatsächlich die Bedeutung, dass man damit die Benennung einer Sache ankündigt.

Streng genommen referenziert das gute alte Sogenannt die Sicht des Systematikers auf eine Sache oder dbzgl. Verhalt, der für diesen immer zuerst eine Aussage einer Person(enmenge) [1] auf eine Sache oder dbzgl. Verhalt darstellt. [2]

HTH
Dr. Webbaer

[1] Stichwort: Erkenntnissubjekt, können auch Bären sein btw
[2] man spricht denn auch von 'Abstraktionsebenen' oder 'Gedankensprüngen' oder 'Schichtwechseln' oder 'Metaphorik'

MartinB· 07.10.11 · 15:30 Uhr

@Ketzu
"Physik ist meiner Meinung nach angewandte Mathematik"
Nein, Physik ist empirisch, Mathe nicht.

Dr. Webbaer· 07.10.11 · 15:42 Uhr

@Dr. B
Die angewandte Mathematik kann empirisch bemessen werden, also auch Algorithmen betreffend und so. Sie wenden ja selbst fortlaufend dementsprechend an - oder hatten Sie mit Ihrem Kommentar jetzt etwas anderes im Auge?!

Ohne Mathematik (μαθηματική τέχνη mathēmatikē téchnē - die Kunst des Lernens) [1] geht's halt naturwissenschaftlich net - wir hatten da schon mal eine diesbezügliche Herausforderung, gell?

HTH
Dr. Webbaer

[1] Mathematik und Zahlenlehre wollen wir hier natürlich nicht gleichsetzen

analphabet· 07.10.11 · 16:20 Uhr

Der Fehler im Bubbelsort-Tanz ist, wenn man ihn tatsächlich so wie Sie ihn aufgeschrieben haben tanzen möchte, ist, dass die Tänzer (vermutlich) zu faul sind. Sie müssten nach dem Algorithmus eigentlich mehr Vergleiche tanzen.
Die 8 dreht sich zum Beispiel nach dem ersten Durchlauf schon um, obwohl sie im nächsten noch einmal dran wäre.

Was ist denn eigentlich mit dem Quicksort?

michael· 07.10.11 · 17:19 Uhr

> (ganz fies grins)

Wieso? Sie ist die einzige Geisteswissenschaft.

Marcus Frenkel· 07.10.11 · 17:29 Uhr

@analphabet
Die Vergleiche stimmen schon, soweit ich das gesehen habe. Mit der 8 haben Sie allerdings recht - die dreht sich einen Durchlauf zu früh; hier liegt der angesprochene Fehler. Herzlichen Glückwunsch. ;)

Quicksort kommt auch noch, in einem späteren Artikel.

Ketzu· 07.10.11 · 21:20 Uhr

Wenn der bubblesort etwas optimiert wird, müssten die Vergleiche auch für die 8 Stimmen, denn wenn der letzte Vergleich ergibt das nicht getauscht werden muss, sind beide an ihrem richtigen Platz. (Denn das vorletzte Element wurde ja bis zum Ende durchgereicht)

Marcus Frenkel· 07.10.11 · 21:29 Uhr

Richtig. Aber ich bezweifle irgendwie, dass das die Absicht der Tänzer war. ;)

Stefan W.· 08.10.11 · 08:13 Uhr

Marcus Frenkel· 07.10.11 · 10:08 Uhr @Stefan W. Das Wort "sogenannte" kann man nicht nur mit Ironischem Unterton benutzen, sondern hat tatsächlich die Bedeutung, dass man damit die Benennung einer Sache ankündigt. Und in dem Sinne ist es hier benutzt. ;)

Sogenannt das sogenannte Wort "sogenannte" kann sogenannt man sogenannt nicht sogenannt nur sogenannt mit sogenanntem ironischem [sogenanntes sic!] sogenanntem Unterton sogenannt benutzen, sogenannt sondern sogenannt hat sogenannt tatsächlich sogenannt die sogenannte Bedeutung, sogenannt dass sogenannt man sogenannt damit sogenannt die sogenannte Benennung sogenannt einer sogenannten Sache sogenannt ankündigt. Sogenannt und sogenannt in sogenannt dem sogenannten Sinne sogenannt ist sogenannt es sogenannt hier sogenannt benutzt.

Wörter benennen immer etwas - das muss nicht angekündigt werden, denn dafür sind sie da, und wäre es nötig, so würde man sich in eine sogenannte Rekursion begeben müssen.

Es ist eine furchtbare Unsitte ständig da ein 'sogenannt' einzufügen, wo man dem Leser vermitteln will, dass er da unbeleckt sein soll. Ganz schlimm im IT-Bereich, wo vor jeden Fachausdruck ein 'sogenannt' platziert wird, als würde man zu Analphabeten sprechen.

Wer ein Wort nicht kennt, der merkt das schon selbst. Das Wort hat überhaupt da nur Sinn, wo es eben fälschlich verwendet wird, und man den Leser darauf aufmerksam machen will. Sonst ist es nur Füllmaterial und ärgerlicher Ballast.

Was man auch immer häufiger sieht, und ein ähnlicher Fehler ist, ist die Verwendung der Phrase 'im wahrsten Sinne des Wortes', wo es genau das nicht ist. "Er ist im wahrsten Sinne des Wortes eine Nachteule." Wahrscheinlich nicht. "Dieser Schiedsrichter ist im wahrsten Sinne des Wortes ein Blinder!" Die Leute hören eine Redewendung, denken nicht darüber nach, und adoptieren sie nach Gefühl. Hier ist das Gefühl, das eine Situation der besonderen Betonung bedarf, also nimmt man einen Ausdruck, den man gehört hat, als etwas besonders betont wurde.

Da hat man einen Ausdruck gehört, als ein etwas fremdartiger Ausdruck verwendet wurde, und stellt diesen auch dem eigenen, etwas fremdartigen Ausdruck voran.

"Die sogenannte friedenserhaltende Maßnahme des Militärs forderte 15 Menschenleben." wäre ein Euphemismus, der die Kennzeichnung verdient haben könnte. Die sogenannte "beiderseitige, einvernehmliche Trennung" wurde, wie unsere Quellen berichten, von Türenschlagen begleitet.

Dr. Webbaer· 08.10.11 · 13:10 Uhr

@Stefan W.

Es ist eine furchtbare Unsitte ständig da ein 'sogenannt' einzufügen, wo man dem Leser vermitteln will, dass er da unbeleckt sein soll.

Das zweimalige 'sogenannt' soll nach Angaben des Autoren in etwa ein 'Wir nennen es nun (so)!" ausdrücken. - Um Verwechselungen mit einem metaphorischen 'Sogenannt' zu vermeiden, schreibt man meist stattdessen 'Dieses Es nennen wir (so).' - Unterschiedliche Kenntnisstände können, müssen aber nicht so hervorgehoben werden. Oder wittern Sie Arroganz?

Ischt ein wenig so wie mit dem 'angeblich', das an sich wertfrei ist, oft aber die Sicht bzw. Aussage einer Person(enmenge) zu einer Sache oder einem dbzgl. Verhalt betont.

Was halten Sie vom guten alten 'sozusagen'?

Dr. Webbaer· 08.10.11 · 22:48 Uhr

off topic - morgen im FAZ-Feuilleton vermutlich erstmals Programmcode!:
http://www.faz.net/aktuell/feuilleton/die-software-von-innen-der-text-des-trojaners-11487209.html

michael· 09.10.11 · 01:35 Uhr

Der Gebrauch von 'sogenannt' im Artikel ist durchaus korrekt. Nachschauen in Wörterbüchern hilft manchmal.
http://www.dwds.de/?kompakt=1&qu=sogenannt

Engywuck· 09.10.11 · 22:56 Uhr

eine ganz nette Seite, mit Veranschaulichung der unterschiedlichen Sortiereffizienz in diversen Szenarien: http://www.sorting-algorithms.com/ (ich hoffe ich greife da nicht zu sehr vor, aber die Volkstanzvideos sind einfach nur grausam...)