StartseiteVon Bits und Bytes

Algorithmen – Bubblesort und Selectionsort

Von / 6. Oktober 2011 / 23 Kommentare / Seite 2 von 2 / Auf einer Seite lesen
Mehr

 

 

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 ∈ Nn → Nn:
(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?

1 / 2
Stichworte: , , ,
Mehr

Kommentare (23)

  1. #1 roghurt
    Oktober 6, 2011

    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.

  2. #2 Rob
    Oktober 7, 2011

    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).

  3. #3 rolak
    Oktober 7, 2011

    ‘Technik’ steht imho von den wenigen verfügbaren Kategorien als einzige nicht in direktem Widerspruch zur IT.
    *zurückhalt* 😉

  4. #4 Stefan W.
    Oktober 7, 2011

    Wieso sprichst Du von

    sogenannten Sortieralgorithmen

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

  5. #5 MartinB
    Oktober 7, 2011

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

  6. #6 Marcus Frenkel
    Oktober 7, 2011

    @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!

  7. #7 Ketzu
    Oktober 7, 2011

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

  8. #8 Ketzu
    Oktober 7, 2011

    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. 🙂

  9. #9 Dr. Webbaer
    Oktober 7, 2011

    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.

  10. #10 Dr. Webbaer
    Oktober 7, 2011

    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’

  11. #11 MartinB
    Oktober 7, 2011

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

  12. #12 Dr. Webbaer
    Oktober 7, 2011

    @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

  13. #13 analphabet
    Oktober 7, 2011

    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?

  14. #14 michael
    Oktober 7, 2011

    > (ganz fies grins)

    Wieso? Sie ist die einzige Geisteswissenschaft.

  15. #15 Marcus Frenkel
    Oktober 7, 2011

    @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.

  16. #16 Ketzu
    Oktober 7, 2011

    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)

  17. #17 Marcus Frenkel
    Oktober 7, 2011

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

  18. #18 Stefan W.
    Oktober 8, 2011

    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.

  19. #19 Dr. Webbaer
    Oktober 8, 2011

    @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’?

  20. #20 Dr. Webbaer
    Oktober 8, 2011

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

  21. #21 michael
    Oktober 9, 2011

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

  22. #22 Engywuck
    Oktober 9, 2011

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

  23. #23 Me
    Juni 3, 2012

    nummer 5 & 6 drehen sich ja bei Bubble gleichzeitig um, obwohl Sie sich ja grade erst verglichen haben? Nur [6] sollte sich umdrehen, und [5] sollte noch einmal verglichen werden XD