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

Samstag 5. Januar 2008, 14:28

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

Samstag 5. Januar 2008, 14:46

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

Samstag 5. Januar 2008, 14:57

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

Samstag 5. Januar 2008, 15:38

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

Samstag 5. Januar 2008, 16:09

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: 28
Registriert: Donnerstag 29. Juni 2006, 18:29
Wohnort: Schweiz
Kontaktdaten:

Samstag 5. Januar 2008, 16:33

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

Samstag 5. Januar 2008, 16:51

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

Sonntag 6. Januar 2008, 12:15

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

Sonntag 6. Januar 2008, 17:40

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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 6. Januar 2008, 17:48

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

Sonntag 6. Januar 2008, 17:50

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

*DUMM*
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 6. Januar 2008, 17:59

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 Modvoice
BlackJack

Sonntag 6. Januar 2008, 18:12

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

Dienstag 8. Januar 2008, 08:55

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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 8. Januar 2008, 09:51

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