Hilfe,wie programmiere ich Bubble-/Trippelsort?!?!?o_O

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.
Antworten
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

Hallo liebes Forum!
Ich bin Schüler der zwölften Klasse und habe in Informatik zum nächsten Freitag eine Projektaufgabe auf,welche wie folgt lautet:

"Zeitanalyse des Sortierens von Listen mit dem Zeitbedarf O(n^2) (mind. 2 Verfahren)"

Dabei wurden mir von meinem Informatiklehrer zwei Verfahren vorgegeben, die wir auch schon behandelt haben, aber leider schon letztes Jahr.
Da ich auch so nicht der beste in Informatik bin, hab ich gehofft, hier auf Hilfe zu stoßen.
Ich will keine Komplettlösung,um Gottes Willen, aber ich brauch die Quelltexte für Bubblesort und Trippelsort,denn die GUI trau ich mir noch halbwegs selber zu. :?

Ich hoffe auf rasche Hilfe und hilfreiche Denkanstöße,DANKE!!!

ciao,tom
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Schon mal mit Google nach "Bubblesort" gesucht?

Du würdest dann auch diese Liste finden, die auch das mir bis dato unbekannte Tripplesort kennt.

Stefan
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

Soweit sogut,stellt sich mir nur noch eine Frage....

Is das legitim,welche Varianter ich von den angegebenen nehme?Denn irgendwie sind für mich da keine oder nur unverständliche Unterschiede zu erkennen :(

Welche der angegeben Quelltexte würdest du denn in Bezug auf die Aufgabenstellung wählen und kann ich die einfach so verwenden oder bedarf es einer Abwandlung?
(ich bin auch nich wirklich in der lage,die da vorhandenen quelltexte so umzuschreiben,dass es glaubwürdig wäre,dass ich die selber geschrieben hab,denn das is echt nur kauderwelsch für mich >_<)
ciao,tom
BlackJack

Dann musst Du das lernen. Alles andere wäre keine Lösung der Hausaufgabe. Eine Beschreibung plus Pseudocode von Bubblesort in Python zu implementieren muss einfach drin sein, weil man sonst den Algorithmus nicht verstanden hat und auch keine Aussagen über die Laufzeit machen kann.
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

mein problem ist nicht,den algorithmus zu verstehen(bubblesort=immer 2 zeichen miteinander vergleichend und dann der größe nach sortierend,oder?!oO)

mein PROBLEM ist einfach das formulieren/implementieren(sprich die schreibweise).........
Benutzeravatar
paedubucher
User
Beiträge: 30
Registriert: Donnerstag 29. Juni 2006, 18:29
Wohnort: Schweiz
Kontaktdaten:

schnitzel hat geschrieben:mein problem ist nicht,den algorithmus zu verstehen(bubblesort=immer 2 zeichen miteinander vergleichend und dann der größe nach sortierend,oder?!oO)

mein PROBLEM ist einfach das formulieren/implementieren(sprich die schreibweise).........
Schau dir mal die C-Version davon an, dann kannst du ja die umschreiben. Ein bisschen Arbeit musst du schon selber leisten :wink:

Tipp:
Beim vertauschen wird im Artikel etwa so vorgegangen:

Code: Alles auswählen

tmp = a
a = b
b = tmp
Mit Python geht es einfacher:

Code: Alles auswählen

a, b = b, a
Viel Glück!
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

boar,da is ja weiter oben sogar n sruktogramm.....ich glaub das könnte ich hinbekommen,danke xD
Benutzeravatar
paedubucher
User
Beiträge: 30
Registriert: Donnerstag 29. Juni 2006, 18:29
Wohnort: Schweiz
Kontaktdaten:

schnitzel hat geschrieben:boar,da is ja weiter oben sogar n sruktogramm.....ich glaub das könnte ich hinbekommen,danke xD
Und, hast du es hinbekommen?
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

hmpf....ich glaub ich hab zu wenig gehirnzellen oder vesteh dieses abstrakte denken nich -.-

naja,ich sitz jedenfalls immer noch dranne >_<

wie schreib ich denn zum beispiel "x von 0 bis arrayobergrenze" in python?!?

und das folgende hast du mir ja schon erklärt,nur wie is denn der algorithmus für trippelsort bzw wiederum,wie schreib ich den?

temp = Array[y]
Array[y] = Array[y+1]
Array[y+1] = temp
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

schnitzel hat geschrieben:wie schreib ich denn zum beispiel "x von 0 bis arrayobergrenze" in python?!?
``range(arraygrenze)``, wobei das was du meinst in Python nicht Array heißt, sondern Liste.

Und das swappen geht so:

Code: Alles auswählen

items[j-1], items[j] = items[j], items[j-1]
Zuletzt geändert von Leonidas am Sonntag 6. Januar 2008, 17:59, insgesamt 1-mal geändert.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

und jetz? for x in range() oder wie?

*DUMM*
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

schnitzel hat geschrieben:for x in range() oder wie?
Ausprobieren?

Ich habe jetzt mal diesen Algorithmus implementiert:

Code: Alles auswählen

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) do:
     for each j in length(A) downto i + 1 do:
       if A[ j -1  ] > A[ j ] then
         swap( A[ j - 1],  A[ j ] )
       end if
     end for
  end for
end procedure
Hat sich herausgestellt, dass eine 1:1 Übersetzung in 5 Zeilen geht.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

Mit anderen Worten: in Python braucht man keine Zeilen für die "Beendung" von Blöcken. :-)
schnitzel
User
Beiträge: 7
Registriert: Samstag 5. Januar 2008, 14:17
Wohnort: Friedland

ich hab da jetz noch ne andere frage...und zwar soll ich dazu ja auch ne grafische oberfläche gestalten und so sieht das bis jetz aus....eher ein prototyp,als alles andere

Code: Alles auswählen

from Tkinter import *
from bubble import *

class oberflaeche(Frame):

    def __init__(self):
        master = None
        Frame.__init__(self, master)
        self.pack()
        self.createwidgets()

    def createwidgets(self):
        self.eingabe = Entry(self)
        self.eingabe.config(width = 60)
        self.eingabe.bind("<KeyRelease>",self.eingabeChange)
        self.eingabe.pack()
        self.sortiert = Label(self, text = "sortierte liste")
        self.sortiert.config(width = 60,bg = "lightgray")
        self.sortiert.bind(self,self.sortiert)
        self.sortiert.pack()
        self.zeit = Label(self, text = "benoetigte zeit")
        self.zeit.config(width= 20,bg = "lightgray")
        self.zeit.place(x = 240, y = 38)
        self.bubbleButton = Button(self, text = "Bubblesort")
        self.bubbleButton.config(bg = "lightgray")
        self.bubbleButton.bind("<Button-1>", self.bubblesort)
        self.bubbleButton.place(x = 20, y= 38)
        self.trippelButton = Button(self, text = "Trippelsort")
        self.trippelButton.config(bg = "lightgray")
        self.trippelButton.bind("<Button-1>", self.trippelsort)
        self.trippelButton.pack()

    def bubblesort(self,event):
        pass
    
    def trippelsort(self,event):
        pass

    def eingabeChange(self, event):
        pass

    def sortiert(self, event):
        return l
def main():
    fenster = oberflaeche()
    fenster.master.title("Zeitanalyse zweier Sortierungsverfahren")
    fenster.mainloop()
main()
so,ausschlaggebend für mich,is mein problem,dass ich das nich hinbekomme,die methode von bubblesort da in irgendeiner art mit einzubinden.....brauche gaaanz dringend hilfe

*noob am werk*

Code: Alles auswählen

def bubblesort(l):
    for passesleft in range(len(l)-1, 0, -1):
        for index in range(passesleft):
            if l[index] < l[index + 1]:
                l[index], l[index + 1] = l[index + 1], l[index]
    return l
und kann mir einer ne funktion nennen,wie ich die zeit ausgeben kann?(siehe label "benoetigte zeit")
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Zeit messen kann man mit dem ``time``-Modul.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

Ein paar Anmerkungen:

Klassennamen sollten mit einem Grossbuchstaben beginnen.

Widgets sollten sich in ihrer `__init__()` nicht selbst `pack()`\en, das machen die Standardwidgets auch nicht. So nimmt man sich die Freiheit das neue Widget in andere ein zu betten.

Innerhalb eines Widgets darf man keine Layout-Manager "mischen", also entweder nur `pack()`, nur `grid()` oder nur `place()`. Wobei man `place()` gar nicht benutzen sollte. Es gibt Ausnahmen, aber die sind sehr selten und nicht für langweilige normale GUIs.

Das Hauptfenster sollte immer eine `Tkinter.Tk()`-Instanz sein. Darauf, das so eine automatisch erzeugt wird, kann man sich nicht verlassen.

Du musst nicht *alles* an das Objekt binden, nur die Sachen auf die man auch aus anderen Methoden noch zugreifen muss.

Die `config()`-Sachen kann man in der Regel auch direkt im Konstruktoraufruf angeben. Also zum Beispiel ``Entry(self, width=60)``.

Um Buttons mit Aktionen zu verbinden benutzt man das `command`-Argument und keine direkte Bindung der Maustaste an die Aktion. Sonst verhalten sich Buttons nicht immer so wie der Benutzer das erwartet.

Für das Zeitproblem gibt's das `time`-Modul. Du musst Dir einfach die Zeit vor dem Aufruf und die danach merken und die Differenz ausgeben.
Antworten