Sortieralgorithmusproblem

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.
Torb

Sortieralgorithmusproblem

Beitragvon Torb » Mittwoch 22. Januar 2003, 18:02

Hallo!
Ich habe vor nicht allzulanger Zeit angefangen mich in Python einzuarbeiten und bin bis jetzt auch begeistert, allerdings wird mein Vorhaben, ein Addressbuch zu programmieren im Moment zurch ein wohl recht simples Problem aufgehalten.
Und zwar habe ich aus seligen Pascal Zeiten einen simplen Sortieralgorithmus, der nun aber nicht die gewünschten Ergebnisse bringt, was ich mir nicht erklären kann :(

Eventuell kann da mal jemand rübergucken und mir die Lösung meines Problems mitteilen ;)

Also ich wollte einfach, dass er die Glieder der Liste jeweils mit den Folgenden vergleicht und wenn diese kleiner sind austauscht.


def Sortier():
z = len(liste)
for i in range(0,z-1):
for j in range(1,z):
if liste[i].nachname > liste[j].nachname:
k = liste[i]
liste[i] = liste[j]
liste[j] = k


Leider gibt er etwa bei den Wörtern

Eva, Adam, Zebra, Xaver diese nicht in der richtigen alphabetischen Abfolge sondern:
Adam, Zebra, Eva, Xaver

kann mir da jemand helfen?

ach ja, die Daten lese ich mit raw_input ein
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Mittwoch 22. Januar 2003, 18:17

tja, zu deinem Vorschlag kann ich nichts sagen, weil die Einrückung fehlt... ich nehme aber mal an, dass du gar nicht nach den Vornamen sortierst, sondern nach den Nachnamen (du vergelcihst nach liste[j].nachname). Wenn es dir nur am sortieren so liegt kann ich dir hiermit helfen:

nimm einfach liste.sort() und die liste wird automatisch sortiert. (Prozedur, gibt keinen wert zurück). Du kannst sort auch eine Funktin übergeben, die bestimmt, wann ein Element größer als das andere ist. Das ist nützlich, falls ein direkter Verglich mit >(=) oder <(=) nicht möglich ist.

Falls du was eigenes willst, kannst du auch bubblesort nehmen:

Code: Alles auswählen

def bubblesort(liste,func=lambda i1,i2:i1>i2):
#func ist eine optionale Funktion, die bestimmt, auf welche Art verglichen werden soll
    anzahl=len(liste)
    vertauscht=1
    while vertauscht:
        vertauscht=0
        for i in xrange(0,anzahl-1):
            if func(liste[i],liste[i+1]):
                liste[i:i+2]=[liste[i+1],liste[i]]
                vertauscht=1
    return liste

Code: Alles auswählen

>>> a=["Eva", "Adam", "Zebra", "Xaver"]
>>> bubblesort(a)
['Adam', 'Eva', 'Xaver', 'Zebra']
Torb

Beitragvon Torb » Mittwoch 22. Januar 2003, 18:53

Vielen Dank!

Das mit der liste.sort() Funktion wusste ich noch gar nicht :)
Naja, jeder war mal Anfänger ;)


Das mit dem Einrücken beim Quote ist wirklich schiefgegangen, sorry

Code: Alles auswählen

def Sortier():
z = len(liste)
for i in range(0,z-1):
    for j in range(1,z):
         if liste[i]> liste[j]:
              k = liste[i]
              liste[i] = liste[j]
              liste[j] = k


So sollte das aussehen!
Nur so fürmich, damit ich meinen Fehler finde, weiß jemand, was daran falsch ist?
Voges
User
Beiträge: 564
Registriert: Dienstag 6. August 2002, 14:52
Wohnort: Region Hannover

Beitragvon Voges » Mittwoch 22. Januar 2003, 20:31

Das soll ja wohl auch der Bubble-Sort sein, oder? Irgendwo habe ich das letztens schonmal gesehen, dass jemand die Laufvariablen *beider* Schleifen für die Sortierung nutze. Die äußere Schleife ist aber doch nur dazu da, die innere häufig genug aufzurufen, und nur in der inneren wird sortiert. Ungetestet:

Code: Alles auswählen

def Sortier():
    z = len(liste)
    for _ in range(0,z-1):
        for j in range(1,z):
            if liste[j-1]> liste[j]:
                k = liste[j-1]
                liste[j-1] = liste[j]
                liste[j] = k

Vielleicht läufts so.
Jan
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Mittwoch 22. Januar 2003, 20:39

test:

Code: Alles auswählen

>>> Sortier([2,1,3,0])
[1, 2, 0, 3]
>>>


wohl noch verbesserungswürdig... ich würde wie bei meinem Bubblesort noch ne Variable einfügen, die festhält ob was vertauscht wurde. Diese Variable wir dann in ner While-Schleife gerufen. Ich nehm mal an, dass es daran lag und so eben nur ein Durchlauf gemacht wurde. dabei wurde noch nicht alles vertauscht. getestet:

Code: Alles auswählen

def Sortier():
    z = len(liste)
    ver=1
    while ver:
        ver=0
        for _ in range(0,z-1):
            for j in range(1,z):
                if liste[j-1]> liste[j]:
                    k = liste[j-1]
                    liste[j-1] = liste[j]
                    liste[j] = k
                    ver=1
Voges
User
Beiträge: 564
Registriert: Dienstag 6. August 2002, 14:52
Wohnort: Region Hannover

Beitragvon Voges » Mittwoch 22. Januar 2003, 21:03

Die while-Schleife macht aber die bisher äußere Schleife überflüssig.

Code: Alles auswählen

def Sortier():
   z = len(liste)
   ver = 1
   while ver:
      ver=0
      for j in range(1,z):
         if liste[j-1]> liste[j]:
            k = liste[j-1]
            liste[j-1] = liste[j]
            liste[j] = k
            ver = 1

Jan
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Mittwoch 22. Januar 2003, 21:04

lol, womit wir bis zu meinem Vorschlag verbessert haben... :lol: Es führen eben alle wege nach Rom. :wink:
RicmanX
User
Beiträge: 69
Registriert: Donnerstag 29. August 2002, 17:10
Wohnort: Erfurt
Kontaktdaten:

Beitragvon RicmanX » Donnerstag 23. Januar 2003, 06:56

Nehmt sort und hört mit Bubblesort auf, das is ja nun echte die schlechteste Sortier-Methode die's überhaupt gibt :lol:
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Donnerstag 23. Januar 2003, 07:48

Ric, es ging aber um sein script zu verbessern, und das hatte das Prinzip von Bubblesort. :lol: Wenn also Bubblesort die schlechteste Methode ist, was ist dann sortieren durch mischen? :wink: :D
Voges
User
Beiträge: 564
Registriert: Dienstag 6. August 2002, 14:52
Wohnort: Region Hannover

Beitragvon Voges » Donnerstag 23. Januar 2003, 08:00

Ich sag nur: mischen impossible :)
SCNR
Jan
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 23. Januar 2003, 14:36

Hi,

also ich würde auf die Vorhandenen Sortiermöglichkeiten von Listen zurückgreiffen, die sind den in Python gecodeten Varianten immer überlegen.


Gruß

Dookie
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 23. Januar 2003, 20:14

hier mal mein Beispiel:

Code: Alles auswählen

liste.sort(lambda x, y: (x.nachname < y.nachname and -1) or (x.nachname > y.nachname and 1))



Dookie
Torb

Beitragvon Torb » Freitag 24. Januar 2003, 10:43

Na da habe ich ja was losgetreten :D

Ich werde mir heute mal alles genau durchlesenund meien Schlüsse daraus ziehen;)

Auf jeden Fall ist das hier ein tolles Forum!
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Dienstag 28. Januar 2003, 01:51

Hallo nochmal,

hab doch glatt die Batterien vergessen :lol:
Ultimate Sortierfunktion mittels bult-in function cmp für Dein Problem:

Code: Alles auswählen

liste.sort(lambda x, y: cmp(x.nachname, y.nachname))



Gruß

Dookie

Wer ist online?

Mitglieder in diesem Forum: WhiteyW