Das deutsche Python-Forum

Hallo alle zusammen!

Ich war mal auf der Suche nach einem schnellen Sortier-Algorithmus und bin bei Heapsort fündig geworden.

Die tests haben ergeben, das er ansich funktioniert. Nichts desto trotz, würde ich euch bitten ihn gründlichst auszutesten, solltet ihr verwendung für das Snippet haben.

Hier ist der Code:

Code: Alles auswählen

#-*- coding: utf-8 -*-
from random import random

def heap_sort(A):
    j = 0
    item = 0
    temp = 0

    for k in xrange(len(A)-1, -1, -1):
        for i in xrange(k+1):
            item = A[i]
            j = i/2
            while (j > 0) and (A[j] < item):
                A[i] = A[j]
                i = j
                j = j/2

            A[i] = item

        temp = A[1]
        A[1] = A[k]
        A[k] = temp
    return A


if __name__ == '__main__':
    l = [random() for x in xrange(0, 10)]
    sl = heap_sort(l)
    print sl

Mir gefällt zwar das ganze Variablenkopieren noch nicht so wunderbar, aber vorerst reichts. Mal schaun, ob ich das noch irgentwie schicker hinbekomme.

MfG EnTeQuAk

Also bei mir liefert deine Implementierung falsche Ergebnisse:

Code: Alles auswählen

>>> x = [random.randint(0, 10) for x in range(10)]
>>> x
[3, 4, 1, 3, 7, 2, 4, 5, 4, 7]
>>> heap_sort(x)
[1, 3, 2, 3, 4, 4, 4, 5, 7, 7]

Dann hätte ich aber noch ein paar Anmerkungen zu deinem Quellcode, falls es dir recht ist

Als ersten Schritt würde ich zu Beginn der Funktion "A" in eine Liste umwandeln, da dies von deiner Implementierung eh benötigt wird. Wo kann man auch Generatoren etc. entgegennehmen:

Code: Alles auswählen

def heap_sort(A):
    A = list(A)     #das hier
    j = 0
    ....

Dann würde ich noch die folgenden drei Zeilen einsparen, da die durchgeführte Initialisierung unnötig ist. Viel schlimmer ist eigentlich, dass du damit unter Umständen Fehler verdeckst, welche korrekterweise durch einen nicht vorhandenen Namen ausgelöst werden sollten:

Code: Alles auswählen

    j = 0
    item = 0
    temp = 0

Und wie du selber schon bemerkt hast, nervt dich das Variablenkopieren. Da gibt es in Python doch eine wunderschöne Lösung, welches "temp" überflüssig macht:

Code: Alles auswählen

i = j
j = j/2

#wird zu
i, j = j, j/2

#und
temp = A[1]
A[1] = A[k]
A[k] = temp

#wird zu
A[1], A[k] = A[k], A[1]

Und wie bei Heapsort so üblich, hat man natürlich noch das Problem, dass die Lösung nicht stabil ist. Das ist natürlich immer Ermessenssache, ob man diese Eigenschaft benötigt oder nicht.

Also Grundsätzlich, erstmal Danke für deine ausführliche Meinung!

EyDu hat geschrieben:Also bei mir liefert deine Implementierung falsche Ergebnisse:
Code: Alles auswählen
>>> x = [random.randint(0, 10) for x in range(10)]
>>> x
[3, 4, 1, 3, 7, 2, 4, 5, 4, 7]
>>> heap_sort(x)
[1, 3, 2, 3, 4, 4, 4, 5, 7, 7]

Das werde ich heute abend, wenn ich Feierabend habe mal genauer unter die Lupe nehmen. Denn die Ergebnisse sehen irgentwie sehr komisch aus (im Gegensatz zu meinen zu Hause).
Mal schaun...

EyDu hat geschrieben: Dann hätte ich aber noch ein paar Anmerkungen zu deinem Quellcode, falls es dir recht ist

Eine der besten Dinge der Welt ist Kritik. Ohne sie kann man nicht dazulernen. Genauso, wie Fehler sehr wichtig sind. Nicht nur sie zu beseitigen.

EyDu hat geschrieben:Als ersten Schritt würde ich zu Beginn der Funktion "A" in eine Liste umwandeln, da dies von deiner Implementierung eh benötigt wird. Wo kann man auch Generatoren etc. entgegennehmen:
Code: Alles auswählen
def heap_sort(A):
    A = list(A)     #das hier
    j = 0
    ....

Sehr gute Idee, daran habe ich noch gar nicht gedacht.

EyDu hat geschrieben:Dann würde ich noch die folgenden drei Zeilen einsparen, da die durchgeführte Initialisierung unnötig ist. Viel schlimmer ist eigentlich, dass du damit unter Umständen Fehler verdeckst, welche korrekterweise durch einen nicht vorhandenen Namen ausgelöst werden sollten:
Code: Alles auswählen
    j = 0
    item = 0
    temp = 0
Und wie du selber schon bemerkt hast, nervt dich das Variablenkopieren. Da gibt es in Python doch eine wunderschöne Lösung, welches "temp" überflüssig macht:
Code: Alles auswählen
i = j
j = j/2

#wird zu
i, j = j, j/2

#und
temp = A[1]
A[1] = A[k]
A[k] = temp

#wird zu
A[1], A[k] = A[k], A[1]

Stimmt, da war doch etwas. Danke, werde ich ändern. (Und Hey, es sieht wirklich schicker aus)

EyDu hat geschrieben:Und wie bei Heapsort so üblich, hat man natürlich noch das Problem, dass die Lösung nicht stabil ist. Das ist natürlich immer Ermessenssache, ob man diese Eigenschaft benötigt oder nicht.

Was bei Zahlen (wofür ich es brauchte) nicht das Problem ist, da ich nur eine einfache Zahlenliste sortiert haben brauchte.
JAAA, ich weiß dazu kann man ''list.sort'' verwenden. Aber man möchte ja lernen und selber machen :=)

Aber grundsätzlich kann ich sagen, das ich irgentwie gefallen an diesem Thema "sortieren & Datenstrukturen" gefunden habe. Mal schaun, was sich da noch so machen lässt. Habe schon viele interessante Dinge gefunden, die keine Python-Implementierung besitzen. (zumindest habe ich nichts gefunden)

Danke erstmal für deine Kritik!

MfG EnTeQuAk

Heapsort geht auch deutlich kürzer:

Code: Alles auswählen

import heapq

def heapsort(sequence):
    return heapq.nsmallest(len(sequence), sequence)

Da könnte ich auch gleich noch meine eigene Listen-Implementierung in Python beisteuern

:

Code: Alles auswählen

mylist = list

Bei der Gelegenheit fällt mir noch ein schöner Ansatz aus dem Cookbook ein: der hier.

Och verdammt. Es hat doch etwas schönes, das die Python-Baterien fast nicht erschöpfbar sind.

Das modul hab ich irgentwie immer übersehen :=)

Danke für diese Lösung

MFG EnTeQuAk