Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Sortieren durch Einfügen / InsertionSort Algorithmus

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
030



Anmeldungsdatum: 02.08.2006
Beiträge: 2
Wohnort: BERLIN

BeitragVerfasst am: 02. Aug 2006 15:49    Titel: Sortieren durch Einfügen / InsertionSort Algorithmus Antworten mit Zitat

Hallo Wink , ich hoffe mir kann jemand bei folgendem Problem weiterhelfen:

Die Aufgabe lautet:

In einem ungeordneten Array der Länge n mögen nur die Schlüsselwerte 0 und 1
vorkommen, nach denen das Array aufsteigend sortiert werden soll.
a) Wie wirkt sich das auf das Worst-Case-Verhalten des „Sortierens durch Einfügen“ aus?
(s. Kap. 3.3.3 des Moduls)
Geben Sie ein Eingabearray an, das diesem Worst Case entspricht, und geben Sie die
Anzahl der für das Sortieren erforderlichen Rechenoperationen an.
b) Geben Sie für ein Array des oben skizzierten Typs einen Sortieralgorithmus an, der das
Sortieren in O(n) Rechenschritten schafft.


Meine Ansätze:
a)
Wie wirkt sich das auf das Worst-Case-Verhalten des „Sortierens durch Einfügen“ aus?
-Die Frage verstehe ich nicht.

Geben Sie ein Eingabearray an, das diesem Worst Case entspricht, und geben Sie die
Anzahl der für das Sortieren erforderlichen Rechenoperationen an.


-bei n=6 wäre ein WorstCaseArray so: {111000}
-wie komme ich jetzt jedoch auf die Anzahl der Rechenoperationen,
das sind doch einerseits die Vergleiche u. andererseits die Zuweisungen bzw. Vertauschungen??Muss man sich den Ablauf des Algorithmus komplett aufschreiben oder gibt es da einen anderen Weg das rauszubekommen?

111000
111000
111000
110100
110100
101100
101100
011100
011100
011010
011010
010110
010110
001110
001110
001101
001101
001011
001011
000111

da komme ich auf 20 "Rechenoperationen"...
stimmt dasoder macht man das anders???
grübelnd traurig
b)- dazu habe ich leider keinen Ansatz...

Ich hoffe es kann mir jemand weiterhelfen...
danke im voraus....
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
as_string



Anmeldungsdatum: 24.02.2006
Beiträge: 80
Wohnort: Heidelberg

BeitragVerfasst am: 03. Aug 2006 00:18    Titel: Antworten mit Zitat

Zur b):
Du machst einen Zeiger auf das erste und das letzte Element. Jetzt schaust Du Dir das Element an, auf den der linke Zeiger zeigt. ist es eine 0 gehst Du zum nächsten eins nach rechts, so lange, bis Du eine 1 gefunden hast. Wenn der linke Zeiger also auf einer 1 steht geht's mit dem rechten weiter. Da gehst Du so lange nach links, bis Du eine 0 gefunden hast, oder bis der rechte Zeiger den linken getroffen hat.
Wenn der rechte Zeiger auf einer 0 steht und der linke auf einer 1, dann vertauschst Du die beiden Elemente und fängst wieder an links die nächste 1 zu finden, dann rechts die nächst 0 oder eben, bis die beiden Zeiger übereinander weg gelaufen sind.

Gruß
Marco
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Senior Sanchez



Anmeldungsdatum: 19.06.2006
Beiträge: 9

BeitragVerfasst am: 04. Aug 2006 20:22    Titel: Antworten mit Zitat

as_string hat Folgendes geschrieben:
Zur b):
Du machst einen Zeiger auf das erste und das letzte Element. Jetzt schaust Du Dir das Element an, auf den der linke Zeiger zeigt. ist es eine 0 gehst Du zum nächsten eins nach rechts, so lange, bis Du eine 1 gefunden hast. Wenn der linke Zeiger also auf einer 1 steht geht's mit dem rechten weiter. Da gehst Du so lange nach links, bis Du eine 0 gefunden hast, oder bis der rechte Zeiger den linken getroffen hat.
Wenn der rechte Zeiger auf einer 0 steht und der linke auf einer 1, dann vertauschst Du die beiden Elemente und fängst wieder an links die nächste 1 zu finden, dann rechts die nächst 0 oder eben, bis die beiden Zeiger übereinander weg gelaufen sind.

Gruß
Marco


Das klingt verdächtig nach Radix-Exchangesort Augenzwinkern
Das Problem ist aber, dass Radix-Exchangesort im allgemeinen aber O(n * lg n) unterliegt. Es ist ja im Grunde nen besseres Quicksort, weil besser geteilt wird, da man sich die Bestimmung eines Pivotelementes spart.

Ich denke aber, dass man es auch gar nicht so kompliziert machen müsste und bits vergleichen muss. Distribution Counting aka BucketSort könnte nämlich schon reichen und besitzt außerdem eine lineare Laufzeitkomplexität. Will mans natürlich noch besser (und speicherschonenender) machen, nimmt man wohl Straight-Radixsort.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
as_string



Anmeldungsdatum: 24.02.2006
Beiträge: 80
Wohnort: Heidelberg

BeitragVerfasst am: 04. Aug 2006 23:09    Titel: Antworten mit Zitat

Hallo Senior Sanchez!

OK. Du hast gewonnen! Wenn ich mal nach einem guten Algorithmus für irgendwas suche, dann frage ich zuerst Dich! Mit Zunge
Ja, irgendwann habe ich mal von diesen ganzen Algorithmen gehört... Im Grunde habe ich mir den Alg. von oben auch auf Basis dieser überlegt. Allerdings bin ich wirklich mehr von der Richtung "Quicksort" gekommen. Eigentlich mache ich nur einen Schritt von Quicksort und wie Du schon richtig schreibst, spare ich mir das Pivotelement und habe danach auch schon eine fertig sortierte Menge, weil es eben nur "größer und kleiner" gibt (also 1 oder 0). Die Laufzeit in diesem Spezialfall ist aber O(n), so dass ich meinen Alg. immer noch ganz i. O. finde, oder?
Bucketsort ist vielleicht anschaulicher, aber sortiert das ganze ja in externe Arrays, was vielleicht wirklich nicht so perfekt für den Speicherbedarf ist. Auf der anderen Seite hat es natürlich dann auch den Vorteil, dass das ursprüngliche Array erhalten bleibt und, dass die Reihenfolge der 0-Elemente und der 1-Elemente untereinander erhalten bleibt, was ja bei meinem Alg. nicht der Fall ist.
Allerdings sind mir die Radix-Sort Alg.s nicht mehr so richtig geläufig. War da nicht was, dass man sich zuerst die niederwertigste Ziffer anschaut, nach der mit einem O(n)-Alg., wie z. B. Bucketsort sortiert und dann die nächste Ziffer und so weiter? War das dann der straight oder...? Aber was würde uns das jetzt bei diesem Problem bringen?
Eigentlich müßte ich jetzt mein Algorithmenbuch rausholen, aber dafür bin ich irgendwie gerade zu faul... Außerdem ist Samstag-Abend! Prost

Gruß
Marco
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Senior Sanchez



Anmeldungsdatum: 19.06.2006
Beiträge: 9

BeitragVerfasst am: 05. Aug 2006 10:44    Titel: Antworten mit Zitat

as_string hat Folgendes geschrieben:
Hallo Senior Sanchez!

OK. Du hast gewonnen! Wenn ich mal nach einem guten Algorithmus für irgendwas suche, dann frage ich zuerst Dich! Mit Zunge
Ja, irgendwann habe ich mal von diesen ganzen Algorithmen gehört... Im Grunde habe ich mir den Alg. von oben auch auf Basis dieser überlegt. Allerdings bin ich wirklich mehr von der Richtung "Quicksort" gekommen. Eigentlich mache ich nur einen Schritt von Quicksort und wie Du schon richtig schreibst, spare ich mir das Pivotelement und habe danach auch schon eine fertig sortierte Menge, weil es eben nur "größer und kleiner" gibt (also 1 oder 0). Die Laufzeit in diesem Spezialfall ist aber O(n), so dass ich meinen Alg. immer noch ganz i. O. finde, oder?


Ja, es könnte für diesen Fall standardmäßig dann eine lineare Komplexität haben, muss aber nicht. Gut, du hast da ein Array als worst-case für Insertionsort, was genau rückwärts sortiert ist. Es wird an dieser Stelle einmal sortiert (also 1er Bit-Zahlen auf der linken Seite mit 0er Bit-Zahlen auf der rechten Seite vertauscht) und das Array somit im Grunde nur gedreht. Trotzdem kann noch eine Unordnung herrschen! Denn es gibt ja auch Zahlen die sind verschieden, aber unterscheiden sich nicht im höchstwertigen Bit, sondern erst in nen paar niederwertigen! Diese werden dabei eben nicht gedreht, weil diese Bits nicht betrachtet wurden. Deshalb ruft sich Radix-Exchangesort dann noch wie Quicksort selbst rekursiv auf, mit veränderten Betrachtungsrahmen und dem nächst kleineren zu betrachtenden Bit. Und das kann am Ende bedeuten, dass es auch für diesen Fall eine O(n * lg n)-Komplexität hat.

as_string hat Folgendes geschrieben:

Bucketsort ist vielleicht anschaulicher, aber sortiert das ganze ja in externe Arrays, was vielleicht wirklich nicht so perfekt für den Speicherbedarf ist. Auf der anderen Seite hat es natürlich dann auch den Vorteil, dass das ursprüngliche Array erhalten bleibt und, dass die Reihenfolge der 0-Elemente und der 1-Elemente untereinander erhalten bleibt, was ja bei meinem Alg. nicht der Fall ist.
Allerdings sind mir die Radix-Sort Alg.s nicht mehr so richtig geläufig. War da nicht was, dass man sich zuerst die niederwertigste Ziffer anschaut, nach der mit einem O(n)-Alg., wie z. B. Bucketsort sortiert und dann die nächste Ziffer und so weiter? War das dann der straight oder...? Aber was würde uns das jetzt bei diesem Problem bringen?
Eigentlich müßte ich jetzt mein Algorithmenbuch rausholen, aber dafür bin ich irgendwie gerade zu faul... Außerdem ist Samstag-Abend! Prost

Gruß
Marco


Ja, genau, Bucketsort arbeitet leider nicht insitu. Aber Straight-Radixsort ist etwas speicherschonenender, bzw. eben eine Verallgemeinerung.

Genau, hast es schon erkannt. Radix-Exchangesort ist quasi ein Quicksort, bei dem die Zahlen immer anhand ihres höchstwertigen Bits, also von links nach rechts quasi gelesen, verglichen werden. Findet der Algorithmus im linken Teil der Folge eine Zahl die am gerade betrachteten Bit eine 1 besitzt, so stoppt er und fängt an im rechten Teil der Folge eine Zahl zu finden, bei der dieses Bit 0 ist. Dann wird vertauscht. Nun ergeben sich durch diese Werte, also wie weit der Algorithmus von links nach rechts gewandert ist, neue Grenzen, für die Exchange-Radixsort sich wieder aufruft. An dieser Stelle durchsucht Exchange-Radixsort dann nur ein Teil des Arrays und vergleicht das nächstkleinere Bit des vorigen Aufrufes, sucht wieder nach diesen bit-päärchen und vertauscht am Ende wieder um sich danach wieder rekursiv aufzurufen.

Daher dann die O(n*lg n) Komplexität, weil im Durchschnitt das Array genau halbiert wird und somit lg n abstiege erfolgen, wie in einem binären Baum.

Straight-Radixsort ist nun eine Verallgemeinerung des BucketSorts oder auch Distribution Counting genannt.

Es iteriert in einer großen Schleife über jedes Bit der Zahlen, diesmal aber von rechts nach links, also mit dem niederwertigsten begonnen.
Wird dabei eine 0 gefunden, so wird in einem hilfsarray "counter" der wert an Index 0 um 1 inkrementiert, wird eine 1 gefunden, so wird der wert an Index 1 um 1 inkrementiert.
Anschließend durchläuft man das ursprüngliche Array rückwärts, testet wieder die Bits und holt sich dann aus dem Hilfsarray "counter" den Wert zum passenden Bit. Dieser Wert aus dem Hilfsarray "counter" dient als neuer Index für ein weiteres Array "temp". An diesen Index wird nun die ursprüngliche Zahl geschrieben und der Wert für den jeweiligen Index im Hilfsarray "counter" dekrementiert. So läuft das ganze dann durch.

Anschließend wird das Originalarray durch Hilfsarray "temp" ersetzt und die gesamte Iteration beginnt von vorne, aber diesmal mit dem nächst höheren Bit.

Es gibt ansich davon auch noch ne Optimierung, indem man nicht nur ein Bit untersucht, sondern gleich mehrere, zum Beispiel 4 bits. Das erhöht aber den Speicherplatz fürs Hilfsarray "counter", da dieses 2^m (m bezeichnet die Anzahl der betrachteten bits, also jetzt 4 --> 16 mögliche Zahlen --> 16 mögliche Indizes) mögliche Indizes besitzen muss.

Das ganze besitzt dann schon ne lineare Komplexität, und zwar für alle möglichen Fälle, nicht nur eventuell für diesen Spezialfall.


Ich glaube aber das die es gar nicht so kompliziert haben wollen Augenzwinkern

Will man einen Algorithmus, der genau diesen Worst-case vom Threadsteller erfüllen soll, so würde ein einfaches umdrehen des Arrays reichen, was wohl garantiert in O(n) laufen sollte.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
030



Anmeldungsdatum: 02.08.2006
Beiträge: 2
Wohnort: BERLIN

BeitragVerfasst am: 09. Aug 2006 16:07    Titel: danke! Antworten mit Zitat

geschockt
Oh , ich versteh leider gar nichts von dem,
was ihr geschrieben habt, ein wenig zu fortgeschritten
würde ich sagen Augenzwinkern ,
Diese Aufgabe oben, die mir gestellt worden ist,
ist die erste Aufgabe zu dem Thema, und ich verstehe
das einfach nicht wie man die Sache mit den Sortieralgorithmen
angehen soll, ....
es wäre sehr nett, wenn jemand auf die obigen Fragen
eingehen könnte und mir das anhand Herleitung erklären könnte,
dann würde ich hoffentlich auch in dem Bereich durchblicken...

Hilfe
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen