Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
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:
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
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
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:
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.
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
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
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.
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
,