Das deutsche Python-Forum

Hey,
erstmal begrüße ich alle Mitglieder des Forums und hoffe das ihr mir ein wenig helfen könnt

,

ich habe versucht selectionsort in Python zu implementieren, allerdings hab ich nen Fehler
eingebaut, den ich nicht finde. Ich weiß dass man den Algorithmus mit nur einer Liste implementieren
kann, allerdings wollte ich es erstmal auf diese Weise probieren hier ist der Quellcode:

Code: Alles auswählen

def selectionsort(list):                #unsortierte Liste als Parameter
    min = list[0]                       #initialisierung des kleinsten Werts
    sorted = []                         #diese Liste soll nachher sortiert sein
    
    while len(list) > 0:                #solange unsortierte Liste nicht leer ist
        for i in range(0, len(list)):   #in dieser Schleife soll der kleinste
            if list[i] < min:           #Wert ermittelt werden
                merke = i
                min = list[i]
        sorted.append(min)              #Hier wird das kleinste Element hinzugefuegt
        del list[merke]                 #und hiert tritt der Indexoutofrangefehler auf

    return sorted

Da gibt es auch noch andere Probleme.

Leere Liste:

Code: Alles auswählen

bj@s8n:~$ python forum8.py
Traceback (most recent call last):
  File "forum8.py", line 23, in <module>
    main()
  File "forum8.py", line 19, in main
    print selectionsort([])
  File "forum8.py", line 4, in selectionsort
    min = list[0]                       #initialisierung des kleinsten Werts
IndexError: list index out of range

Liste mit einem Element:

Code: Alles auswählen

bj@s8n:~$ python forum8.py
Traceback (most recent call last):
  File "forum8.py", line 23, in <module>
    main()
  File "forum8.py", line 19, in main
    print selectionsort([42])
  File "forum8.py", line 13, in selectionsort
    del list[merke]                 #und hiert tritt der Indexoutofrangefehler auf
UnboundLocalError: local variable 'merke' referenced before assignment

Das letzte wird auch das Problem mit dem `IndexError` sein. Wie Du siehst wird `merke` nicht bei jedem Durchlauf der ``while``-Schleife an einen neuen Wert gebunden. So kann es also auch passieren das im vorhergehenden Durchlauf `merke` an die Länge vor dem Entfernen des Elements gebunden wurde und dann im nächsten Durchlauf einen Index enthält, der zu gross ist.

Ok, danke ich habe das Problem mit einem und null Elemente durch eine if-Abfrage vor der Schleife gelöst,
,denke aber das der Code insgesamt noch eleganter zu lösen ist:

Code: Alles auswählen

def selectionsort(list):                    #unsortierte Liste als Parameter
    if len(list) == 0 or len(list) == 1:
        return list

    min = list[0]                           #initialisierung des kleinsten Werts
    sorted = []                             #diese Liste soll nachher sortiert sein
    merke = 0
    while len(list) > 0:                    #solange unsortierte Liste nicht leer ist
        min = list[0]
        iflist = False
        for i in range(0, len(list)):       #in dieser Schleife soll der kleinste
            if list[i] < min:               #Wert ermittelt werden
                iflist = True
                merke = i
                min = list[i]
        sorted.append(min)                  #Hier wird das kleinste Element hinzugefuegt
        if iflist == True:
            del list[merke]             
        else: del list[0]
    return sorted

Boah, ich hab irgendwie viel zu lange für so ne Kleinigkeit gebraucht, ich hoffe das verbessert sich noch mit der Zeit.
Vielen Dank für die Hilfe

@Pierce: Die Bedingung am Anfang kannst Du weglassen wenn der Rest entsprechend geschrieben wird.

`iflist` ist ebenfalls überflüssig. Du musst nur dafür sorgen das `merke` an der richtigen Stelle den Wert zugewiesen bekommt, der zum entfernen verwendet wird, falls es innerhalb der ``for``-Schleife nicht neu gebunden wird. Kleiner Tipp: `merke` ist immer der Index an dem der Wert von `min` in der Liste steht. Wenn das in Deinem Code immer synchron bleibt, brauchst Du `iflist` nicht.

Vergleiche mit literalen Wahrheitswerten sind überflüssig. `iflist` ist entweder `True` oder `False`, dass heisst die Bedingung lautet dann ``True == True`` oder ``False == True``. Das Ergebnis davon ist aber wieder genau das selbe, was `iflist` schon ist.

Statt `range()` solltest Du besser `xrange()` verwenden, oder noch besser die `enumerate()`-Funktion um Index *und* Wert zu erhalten.

Alle Objekte werden im Kontext einer Bedingung, also bei auch bei ``while``, in einen Wahrheitswert umgewandelt. Leere Listen sind dabei "Falsch" und nicht-leere Listen sind "Wahr". Man könnte also auch einfach ``while list:`` schreiben.

An der Namensgebung könntest Du arbeiten. `list`, `min`, `sorted` sind Namen von eingebauten Funktionen/Typen. `iflist` und `merke` sind schlechte Namen, weil sie nicht wirklich darüber informieren was die Bedeutung des Wertes ist, der sich dahinter verbirgt. `merke` könnte man zum Beispiel treffender `min_index` nennen. Mischen von Englisch und Deutsch sieht IMHO unschön aus.

So hab mir jetzt die Zeit genommen, dass ganze wieder zu überarbeiten

Code: Alles auswählen

def selectionsort(array):                    #unsortierte Liste als Parameter
    if len(array) == 0:
        return array

    minimum = array[0]                       #initialisierung des kleinsten Werts
    sortedlist = []                          #diese Liste soll nachher sortiert sein
    min_index = 0

    while array:                             #solange unsortierte Liste nicht leer ist
        minimum = array[0]
        min_index = 0
        for i in xrange(0, len(array)):       #in dieser Schleife soll der kleinste
            if array[i] < minimum:               #Wert ermittelt werden
                min_index = i
                minimum = array[i]
        sortedlist.append(minimum)                   #Hier wird das kleinste Element hinzugefuegt
        del array[min_index]                  #und hiert tritt der Indexoutofrangefehler auf
    return sortedlist

Ich glaub die wichtigsten Punkte hab ich abgedeckt nur das Problem mit der Leeren Liste und der if Abfrage hab ich behalten.
Danke BlackJack, das ist genau die Hilfe die ich brauche, Tipps zum verbessern aber nicht einfach gleich die Lösung vorgesetzt bekommen

@Pierce: Wann werden denn die Werte die an `minimum` und `min_index` vor der Schleife gebunden werden, jemals benötigt!?

upps,stimmt schnell raus damit, danke,

Code: Alles auswählen

def selectionsort(array):                     #unsortierte Liste als Parameter

    sortedlist = []                           #diese Liste soll nachher sortiert sei

    while array:                              #solange unsortierte Liste nicht leer ist
        minimum = array[0]
        min_index = 0
        for i in xrange(0, len(array)):       #in dieser Schleife soll der kleinste
            if array[i] < minimum:            #Wert ermittelt werden
                min_index = i
                minimum = array[i]
        sortedlist.append(minimum)            #Hier wird das kleinste Element hinzugefuegt
        del array[min_index]                  #und hiert tritt der Indexoutofrangefehler auf
    return sortedlist

So sollte es aber passen, oder?

Du hast da einen ganz fiesen Beigeschmack: Du zerstoerst die uebergebene Liste.

Mal drei Moeglichkeiten:
1. Du arbeitest auf einer Kopie und zerstoerst diese,
2. du sortierst pseudo-inplace, d.h. du packst vor das `return` ein `array[:] = sortedlist` oder
3. du aenderst den Algorithmus und haelst irgendwo fest welche Elemente du schon benutzt hast.

Und noch was zum Code:

Code: Alles auswählen

for i in xrange(0, len(array)):       #in dieser Schleife soll der kleinste
    if array[i] < minimum:            #Wert ermittelt werden
        min_index = i
        minimum = array[i]

zu

Code: Alles auswählen

for i, element in enumerate(array):       #in dieser Schleife soll der kleinste
    if element < minimum:            #Wert ermittelt werden
        min_index = i
        minimum = element

Ok danke,

ich weiß das man ihn in-place implementieren kann und dass die übergebene Liste zerstört wird, was nicht so schön ist.
Allerdings habe ich nicht vor den Algorithmus zu verwenden, sondern ich habs aufgrund Übungszwecke programmiert .
Ich werde versuchen ihn noch als in-place-Algorithmus zu implementieren.

enumerate() werd ich mir merken ist ziemlich nützlich

Das deutsche Python-Forum

Selectionsort: IndexoutofRange Error, finde den Fehler nicht

Selectionsort: IndexoutofRange Error, finde den Fehler nicht

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n

Re: Selectionsort: IndexoutofRange Error, finde den Fehler n