h1

Sortieralgorithmik in Python – Teil1 Bubblesort

Oktober 29, 2008

Wie der Titel schon unschwer erkennen lässt, startet hiermit eine kleine Serie, die euch in die Sortieralgorithmen einführt.

Dabei wird jeden Tag ein Artikel mit einem Sortierverfahren veröffentlicht. Die Reihenfolge geht dabei von extrem langsam nach sehr schnell.

Wir starten heute mit einem der langsamsten Sortieralgorithmen überhaupt: Bubblesort

Funktionsweise:
Bubblesort ist ein stabiler Sortieralgorithmus
Es werden der Reihe nach benachbarte Elemente des zu sortierenden Objekts vertauscht. Dieser Vorgang wird solange wiederholt, bis die Liste komplett sortiert ist. Dazu benötigt man in der Regel mehrere Durchläufe.
Hier ein Bild zur verdeutlichung des Schemas: http://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif

Implementierung in Python

#BubbleSort Python

def bubblesort(sequenz):

	durchlaeufe = len(sequenz)

	while durchlaeufe >= 1:

		for k in range(len(sequenz) - 1):

			if sequenz[k] > sequenz[k+1]:

				temp = sequenz[k]

				sequenz[k] = sequenz[k+1]

				sequenz[k+1] = temp

		durchlaeufe = durchlaeufe - 1

	return sequenz

Um nun damit auch etwas sortieren zu können, fügen wir noch folgenden Code zum erstellen einer Zufallsliste mit Zahlen hinzu:

import random
import time

und nach der Definition der Funktion

for rand in range(10000):

	rand = random.randint(1,10000)

	list.append(rand)

zeit1 = time.clock()

result = bubblesort(list)	

zeit2 = time.clock()

print result

print "Berechnungszeit: ",zeit2 - zeit1,"s"

Ich habe auch gleich noch eine kleine Zeitmessung für die Ausführung der Funktion mit eingefügt, damit wir das ganze später auch mit den andren Algorithmen vergleichen können.

Hier also eine kleines Benchmark:

100 Datensätze : 10ms
1000 Datensätze : 410ms
10000 Datensätze : 40.19 s
100000 Datensätze : Das hat einfach zu lange gedauert😉 (über 15min)

Wer mehr über Bubblesort erfahren will: http://de.wikipedia.org/wiki/Bubblesort

Morgen kommt: Selectionsort…

3 Kommentare

  1. nette sache. müssten 100 000 einträge nicht ca 4000 sekunden, also ca. 66 minuten brauchen wenn man die liste mal so fortsetzt? oder täuscht das? das es bei 100 Datensätzen 10 statt 4 ms sind würde ich jetzt einfach mal als abweichung abstempeln, weil es noch so kleine werte sind…


  2. aso


  3. Bei mir tritt einer Fehler auf, das er bei :

    for rand in range(10000):

    rand = random.randint(1,10000)

    list.append(rand)

    folgende Fehler Meldung ausgibt.

    TypeError: descriptor ‚append‘ requieres a ‚list‘ object but recieved a ‚int‘

    muss ich evtl. vorher einen cast auf rand anweden?



Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: