Einfache Sortieralgorithmen < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:43 Fr 10.11.2006 | | Autor: | Teufel |
Hallo!
Ich wollte nur fragen, ob mir jemand nochmal die einfachen Sortieralgorithmen wie Einfügesort (Insertion Sort) und Auswahlsort (Selection Sort) erklären könnte! Und vielleicht noch Bubble- & Ripplesort vorsichtshalber mit ;)
Oder ist das so richtig:
Sagen wir, dass die zu sortierenden Feldelemente folgende sind:
A G H B X D D
Bubble Sort:
A G H B X D D
A G B H X D D
A G B H D X D
A G B H D D X
A B G H D D X
A B G D H D X
A B G D D H X
A B D G D H X
A B D D G H X
Ich wollte fragen, ob das so stimmen würde.
Und Ripplesort funktioniert genauso, nur dass das größte nach rechts geht, oder?
Auswahlsort:
A G H B X D D
Das kleinste Feldelement wird gesucht und mit dem 1. vertauscht
A G H B X D D
Das nächstkleinere wird gesucht und an 2. Stelle gesetzt u.s.w....
A B H G X D D
A B D G X H D
A B D D X H G
A B D D G H X
Und bei Einfügesort weiß ich das nicht so genau...
Könnte mir das auch nochmal jemand erklären? Also zusätzlich zud er Erklärung, wie das Programm dann die Buchstaben ordnen würde.
Vielen Dank!
PS: Bitte einfache Erklärungen :) Dann lieber nicht so exakt wie möglich, sondern nur, dass man das Prinzip versteht.
|
|
| |
|
Hallo Teufel!
> Oder ist das so richtig:
>
> Sagen wir, dass die zu sortierenden Feldelemente folgende
> sind:
> A G H B X D D
>
> Bubble Sort:
> A G H B X D D
> A G B H X D D
> A G B H D X D
> A G B H D D X
>
> A B G H D D X
> A B G D H D X
> A B G D D H X
>
> A B D G D H X
> A B D D G H X
>
> Ich wollte fragen, ob das so stimmen würde.
Ja, das ist richtig so. Man fängt vorne an und vergleicht immer zwei "Zahlen", und wenn sie in der falschen Reihenfolge sind, werden sie vertauscht. Und ![[]](/images/popup.gif) hier siehst du noch eine Möglichkeit, wie du deutlich machen kannst, was du gerade gemacht hast (falls das eine Art Hausaufgabe oder so ist, dass dein Lehrer nachvollziehen kann, was du gemacht hast).
> Und Ripplesort funktioniert genauso, nur dass das größte
> nach rechts geht, oder?
Ripplesort kenne ich nicht, aber nach der Beschreibung hier (unter Verfahren) sieht es so aus, als ginge es so, wie du schreibst. 
> Auswahlsort:
> A G H B X D D
>
> Das kleinste Feldelement wird gesucht und mit dem 1.
> vertauscht
>
> A G H B X D D
>
> Das nächstkleinere wird gesucht und an 2. Stelle gesetzt
> u.s.w....
>
> A B H G X D D
> A B D G X H D
> A B D D X H G
> A B D D G H X
Auch diesen Algorithmus kannte ich vorher nicht (jedenfalls nicht unter diesem Namen), aber dank Wikipedia habe ich wieder was gelernt.  Das kommt mir auch richtig vor, was du gemacht hast. ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> Und bei Einfügesort weiß ich das nicht so genau...
>
> Könnte mir das auch nochmal jemand erklären? Also
> zusätzlich zud er Erklärung, wie das Programm dann die
> Buchstaben ordnen würde.
Auch diesen Algorithmus kenne ich nicht (oje, was lernen wir denn im Studium? ) und ich weiß auch nicht, was genau du erklärt haben möchtest. Deshalb sage ich dazu mal nichts und überlasse das jemandem anders.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:42 Sa 11.11.2006 | | Autor: | Teufel |
Danke erstmal für die Hilfe :)
Naja, ich glaube dass man diese einfachen Sortieralgorithmen nicht sooo häufig braucht... und wenn ich wenige Sachen sortieren will, würde ich immer auf Bubblesort zurückgreifen ;)
Wir hatten sogar noch Bucketsort, was ich auch ziemlich cool finde.. aber das hab ich mir selbst erklärt :) Wenn du das auch nicht kennst: Der Algorithmus is praktisch wenn man wenig verschiedene Feldelemente hat. Also wenn du 7632547534634 Ziffern von 0 bis 9 ordnen solltest, würde Bucketsort richtig auftrumpen :)
Aber bei 10 Zahlen von 1-1000 würde Bucketsort recht lange brauchen.
Kann dir ja mal irgendwann ein Beispielquellcode abtippen, wenn's dich interessiert :)
Aber nun zu meinem eigentlichen Problem:
Ich müsste nur wissen (in Worten) wie die einzelnen Algorithmen funktioneren. Am besten an meinen Beispielbuchstaben da :)
Also so, wie ich versucht habe sie zu beschreiben (was vielleicht auch nicht richtig ist bei einigen Algorithmen). Bei Bubblesort z.B., dass immer 2 benachbarte Feldelemente miteinander verglichen werden und, wenn das rechte kleiner ist als das linke, getauscht werden.
Bei Einfügesort (Insertion Sort) war das glaube fast wie bei Auswahlsort, wenn ich mich recht erinnere. Nur, dass dort die Feldelemente in eine sortierte und in eine unsortierte Hälfte eingeteilt wurden. Ich glaube, dass man sich das 1. Element der unsortierten Hälfte genommen hat, und sie in die sortierte Hälfte gepackt hat.
Mal wieder mit den Buchtaben:
A G H B X D D
A | G H B X D D
(der | trennt sortierte und unsortierte Hälfte)
Dann nimmt man sich wieder das 1. Element, was in der unsortierten Hälfte steht (bzw. das 2. Element insgesamt, wenn man diese Aufteilung weglässt), also das G. Das wird dann mit den sortierten Feldelementen verglichen und dort eingeordnet.
A G | H B X D D
Nun würde das H kommen.
A G H | B X D D
Nun zum B. Es wird sich genommen, und durch Vergleiche wird herausgefunden, dass es hinter das A gehört. Und dann werden alle Feldelemente zwischen A und B um eins nach rechts geschoben und das B wird in die Lücke eingefügt.
A B G H | X D D
A B G H X | D D
Nun soll das 1. D hinter das B. Also werden alle Feldelemente zwischen B und dem 1. D eins nach rechts verschoben und das D wird hinter dem B eingefügt.
Also:
A B _ G H X D
Also der Platz wird sozusagen freigeräumt, und nun kommt das D in die Lücke (bei der Stelle mit dem B war es das gleiche, aber da hab ich diesen Schritt mal ausgelassen).
A B D G H X | D
Das gleiche fast nochmal:
A B D D G H X
So... so viel zu meiner Theorie. Stimmt das so?
|
|
|
| |
|
Hallo Teufel,
> Also so, wie ich versucht habe sie zu beschreiben (was
> vielleicht auch nicht richtig ist bei einigen Algorithmen).
> Bei Bubblesort z.B., dass immer 2 benachbarte Feldelemente
> miteinander verglichen werden und, wenn das rechte kleiner
> ist als das linke, getauscht werden.
Ja, das ist die Grundidee. ![[ok]](/images/smileys/ok.gif "[ok]")
> Bei Einfügesort (Insertion Sort) war das glaube fast wie
> bei Auswahlsort, wenn ich mich recht erinnere. Nur, dass
> dort die Feldelemente in eine sortierte und in eine
> unsortierte Hälfte eingeteilt wurden.
> Mal wieder mit den Buchtaben:
>
> A G H B X D D
> [..]
> So... so viel zu meiner Theorie. Stimmt das so?
Ich denke schon, obwohl man es natürlich auch variieren könnte
Also die einfachen Schritte in Kürze:
|A G H B X D D
...
A G H| B X D D
So und statt hier das B an die Stelle von G zu setzen und dabei alle Elemente um 1 nach rechts zu verschieben, könnte man doch auch B und G vertauschen:
A B H| G X D D
Nach dem Tausch geht der Algo nicht sofort zum nächsten Element sondern prüft nochmal, ob das aktuelle Element (jetzt G) eingeordnet werden muß, und vertauscht hier wieder H <-> G (danach wieder prüfen, aber diesmal geschieht nichts)
A B G H| X D D
A B G H X| D D
A B D H X| G D (G <-> D)
A B D G X| H D (G <-> H)
A B D G H| X D (X <-> H)
A B D G H X| D
... noch 3 Schritte ...
A B D D G H X|
Aber ich glaube, daß diese Variation doch eher ein anderer Algorithmus ist als EinfügeSort. Könnte eine Abwandlung von BubbleSort sein, weil's genauso ineffizient zu sein scheint... . Aber deine Beschreibung war denke ich richtig.
Viele Grüße
Karl
Ich frage mich, ob es auch Sortieralgorithmen mit einem "Shift" gibt.
Also das ist der gewöhnliche BubbleSort:
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
2 3 1 4
2 1 3 4
1 2 3 4
und hier ist mal eine abgewandelte Version von BubbleSort. Die Idee ist die zu sortierende Folge in Paare zu zerlegen und zwar so:
4 3 2 1
3 4 1 2 <>
3 1 4 2
1 3 2 4 <>
1 2 3 4 (Es folgen noch 2 sinnlose aufrufe)
Scheint etwas weniger Schritte zu ergeben. Allerdings weiß ich jetzt so "aus dem Bauch heraus " auch nicht, ob es jede Folge sortieren kann... . Also ob die Abbruchbedingung die entgültige Sortierung sicherstellt.
]
|
|
|
|
