Swap Sort

Code-Stücke können hier veröffentlicht werden.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Swap Sort

Beitragvon Nocta » Sonntag 15. März 2009, 14:51

Ich hab mir auf Wikipedia den Swap Sort Algorithmus angeguckt und habe ihn dort in den Sprachen Java, Ada und Haskell vorgefunden.
Mein erster Gedanke war: Aber jetzt auch mal in Python ;)
Man muss seine Lieblingssprache ja irgendwie verbreiten.

Fragen:
1.

Code: Alles auswählen

def swap_sort(sortme):
    index = 0
    while index < len(sortme) - 1:
        new_index = sum(1 for x in sortme if x < sortme[index])
        if index == new_index:
            index += 1
        else:
            sortme[index], sortme[new_index] = sortme[new_index], sortme[index]
    return sortme

Der Code ist so doch okay, oder?

2. Die Quelltexte der anderen Sprachen sind nur in <code>-Tags, also farblos, ich würde den Python-Code aber gerne in Farbe haben. Wär's irgendwie asozial, wenn ich da jetzt <source lang="python"> benutzen würde? Oder wär das in Ordnung, wenn ich die anderen dafür auch farbig mache? :p

3. Wär's sehr asozial, wenn ich Python an den Anfang statt an's Ende bringen würde? :p


Ich hab bisher noch nie was auf Wikipedia geändert und kenne deshalb auch keine Vorschriften oder so. Ich will nur nicht direkt irgendwie gelöscht werden oder sonstwas.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Re: Swap Sort

Beitragvon Leonidas » Sonntag 15. März 2009, 15:06

Nocta hat geschrieben:2. Die Quelltexte der anderen Sprachen sind nur in <code>-Tags, also farblos, ich würde den Python-Code aber gerne in Farbe haben. Wär's irgendwie asozial, wenn ich da jetzt <source lang="python"> benutzen würde? Oder wär das in Ordnung, wenn ich die anderen dafür auch farbig mache? :p

Ja, Syntax-Highlighting ist eigentlich immer gut, finde ich.

Nocta hat geschrieben:3. Wär's sehr asozial, wenn ich Python an den Anfang statt an's Ende bringen würde? :p

Die sind alphabetisch und wenn es keinen Grund gibt das zu ändern würde ich dabei bleiben.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Beitragvon hendrikS » Sonntag 15. März 2009, 15:32

Von einem Projekt sind die 9 Zeilen jedoch weit entfernt. Ich finde es schade, wenn der Showcase mit Codesnippets überladen wird.

Edit (Leonidas): Ack, verschoben.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Sonntag 15. März 2009, 16:25

@hendrikS sorry, darüber hatte ich gar nicht nachgedacht, das ist natürlich nur ein Codesnippet was man mal nebenbei in 5 Minuten schreibt.

Da Leonidas nicht auf 1) geantwortet hat, gehe ich mal davon aus, dass man den Code so stehen lassen kann und poste das jetzt mal in Wikipedia.

Edit: Vielleicht ist new_index nicht ganz so gut gewählt?
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Sonntag 15. März 2009, 19:02

Hallo,

ich würde das nicht in einer while-Schleife machen, sondern iterativ:

Code: Alles auswählen

#!/usr/bin/env python
"""
    An implementation of the swap sort algorithm[1] in Python.

    [1] http://de.wikipedia.org/wiki/Swap-Sort
"""
def swapitems(array, old, new):
    old_item = array[old]
    array[old] = array[new]
    array[new] = old_item
    return array

def swapsort(array):
    for i, elem in enumerate(array):
       array = swapitems(array, i, len([e for e in array if e < elem]))
    return array

if __name__ == '__main__':
    print swapsort([7, 8, 5, 2, 4, 9, 3, 1])
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Sonntag 15. März 2009, 19:23

Dauerbaustelle hat geschrieben:ich würde das nicht in einer while-Schleife machen, sondern iterativ:

Iterativ = Schrittweise = In Schleifen = Auch while ;)
Du kommst bestimmt wegen "iterieren" darauf, oder?

Warum machst du swapitems()? Ich fand gerade hier konnte man im Gegensatz zu den anderen 3 Sprachen eine Stärke von Python zeigen: a, b = b, a

Über for oder while kann man sich sich eventuell streiten, ich fand aber 1. die while-Schleife verständlicher und 2. ist diese näher an der Beschreibung des Algorithmus am Anfang der Wikipediaseite. Ich wüsste intuitiv/ohne Nachzudenken gar nicht, wie ich das mit einer for-Schleife lösen soll. Du anscheinend auch nicht, denn dein Algorithmus ist falsch bzw. zumindest nicht der Swap Sort Algorithmus ;)
print swapsort([7, 8, 5, 236, 123, 2, 4, 9, 3, 1, 34, 234])
=> [1, 4, 3, 234, 5, 7, 8, 9, 34, 2, 123, 236]
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Sonntag 15. März 2009, 19:41

Okay, dann so:

Code: Alles auswählen

def swapsort(array):
    for i, elem in enumerate(array):
        newindex = len([e for e in array if e < elem])
        if newindex != i:
            array[i], array[newindex] = array[newindex], array[i]
    return array


Das ist aber auch nicht richtig, seltsam... ich verstehe nicht, was ich da falsch gemacht habe?
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Sonntag 15. März 2009, 20:21

Ich hab mir das jetzt nicht genau angeguckt aber ich denke wegen dem Teil:

Code: Alles auswählen

if index == new_index:
            index += 1


Der Index geht nicht bei jedem Schritt eins hoch ;)
Deshalb finde ich da eine for-Schleife auch nicht so vorteilhaft.
Schau dir mal das Beispiel bei Wikipedia an.
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Sonntag 15. März 2009, 20:36

Oh, klar! Dann kann man das natürlich nicht mit einer for-Schleife machen.

Würde aber das nicht mit sum(...) sondern mit len(...) machen. Sieht toller aus ^^
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Sonntag 15. März 2009, 20:39

Mhm und dann schmink ich die Funktion noch n bisschen oder wie? :p
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Sonntag 15. März 2009, 21:21

Rüschen!
BlackJack

Beitragvon BlackJack » Sonntag 15. März 2009, 21:57

Bei `len()` muss man aber dauernd temporär Listen erstellen, nur um dann deren Länge zu ermitteln. Da ist die `sum()`-Variante effizienter.
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Sonntag 15. März 2009, 22:36

Ich wusste doch dass ich Recht habe. BlackJack, man siehe und staune:

Mit sum(...):
time python swapsort.py
real 0m0.252s
user 0m0.220s
sys 0m0.020s

time python swapsort.py
real 0m0.254s
user 0m0.232s
sys 0m0.012s

time python swapsort.py
real 0m0.266s
user 0m0.248s
sys 0m0.000s

time python swapsort.py
real 0m0.254s
user 0m0.240s
sys 0m0.008s

Ergibt Ø 0,256s


Mit len(...):
time python swapsort.py
real 0m0.247s
user 0m0.224s
sys 0m0.004s

time python swapsort.py
real 0m0.245s
user 0m0.228s
sys 0m0.004s

time python swapsort.py
real 0m0.236s
user 0m0.212s
sys 0m0.016s

time python swapsort.py
real 0m0.236s
user 0m0.216s
sys 0m0.008s

Ergibt Ø 0,241s


Code war dieser: http://paste.pocoo.org/show/108090/

Hihi :D
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Sonntag 15. März 2009, 22:46

Und was soll das beweisen? 4 Durchläufe jeweils, das ist keine aussagekräftige Sample-Größe.

Ich finde übrigens auch das ``sum()`` rein muss, schon allein deswegen weil es das in anderen Sprachen oft nicht gibt :twisted:
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Sonntag 15. März 2009, 22:59

Deine Aussage war `len()` sieht toller aus. Das finde ich nicht. Das lässt sich auch mit einem Benchmark nicht ändern. Ich frage mich hier eher warum `sum()` langsamer ist, und wage mal zu behaupten, das ist kein Unterschied auf den man sich verlassen sollte.

Der Test hat übrigens noch den Schönheitsfehler, dass er einmal die Listen sortiert und dann neunmal auf bereits sortierten Listen operiert.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder