h1

Sortieralgorithmik in Python Teil2 – Selectionsort

Oktober 31, 2008

Heute werden wir uns geschwindikeitsmaßig ein wenig steigern, denn es folgt Selectionsort!

Doch zuerst einmal das Prinzip:

Man stelle sich vor S sei der sortierte Teil einer Liste und U der Unsortierte, deshalb ist bei einer unsortierten Sequenz der S Teil anfangs leer.
Beim Aufruf der Funktion wird nun das kleinste Element der Liste herausgesucht und an den Anfang gesetzt. So wird der Reihe nach die ganze Liste durchgelaufen, bis die Liste sortiert ist!

Hier ein Bild zum Verständnis des Prinzips:

Selectionsort

Selectionsort

Hier die Standardimplementation in Python inklusvie Zeitmessung und automatisch erzeugter Liste:

# SelectionSort Python
  2 import random
  3 import time
  4
  5 def selectionsort(seq):
  6     for k in range(len(seq) - 1):
  7         j = i = k
  8         for i in range(k, len(seq)):
  9             if seq[i] < seq[j]:
 10                 j = i
 11         seq[j], seq[k] = seq[k], seq[j]
 12     return seq
 13
 14 list = []
 15 for rand in range(100000):
 16         rand = random.randint(1,100000)
 17         list.append(rand)
 18
 19 zeit1 = time.clock()
 20 ausgabe = selectionsort(list)
 21 zeit2 = time.clock()
 22 print ausgabe
 23 print zeit2-zeit1,"s"

Benchmark:
1000 Datensätze : 130ms
10000 Datensätze : 12.81s
100000 Datensätze : 1749.96s

und Morgen: Mergesort..

7 Kommentare

  1. Die Beispiele zu Bubble- oder SelectionSort gehen davon aus, dass es schon eine Liste gibt wie [1,2,3,…], die dann nur noch sortiert werden muss. – Also im Prinzip [1,2,3,…].sort()
    Und wie machst du’s als rekursive Sortiermethode von Listenelementen?


  2. lolololol ihr sied alle noobs kauft euch ein Leben


  3. Radikal


  4. Pyrotechnik ist kein Verbrechen


  5. Mehr Toleranz für Homoschwuchteln
    Kennt ihr Akwasi?


  6. Ne du?


  7. Gehst steil digger gönn dir mal hart



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: