Pivot partitioning by scanning

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Pivot partitioning by scanning

Beitrag von AnnaW »

Hallo,

ich habe eine Verständnisfrage zur Übung 5, Aufgabe 2.

Dort haben wir die Sequenz: {3, 4, 9, 2, 6, 5, 1, 2, 3} und das Pivot-Element 3.

\(m_1\) wird erst auf 1 gesetzt und dann für jedes Element das kleiner als 3 ist, um eins erhöht. Also ist \(m_1= 1 + 3 = 4\).
\(m_2 = m_1\) und wird für jedes Element größer als 3 um eins erhöht. Also ist \(m_2 = 4 + 4 = 8\).

Demnach zeigt mein \(m_1\) auf die erste 2 und mein \(m_2\) auf die letzte 2. Oder fangen wir doch bei 0 an zu zählen und \(m_1\) zeigt auf die 9 und \(m_2\) auf die 1? Das würde meiner Meinung nach mehr Sinn ergeben, da dann ja nach \(m_1\) und vor \(m_2\) nur Pivot-Elemente kommen. Bzw. Stimmt das auch nicht ganz, \(m_2\) würde so auf das 2. Element der rechten Liste zeigen. Ich bin verwirrt ^^ Kann mir bitte jemand erklären, wie die Pointer genau gesetzt werden?

Viele Grüße

Anna

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Pivot partitioning by scanning

Beitrag von JannikV »

Hey,

plump gesagt werden die Hilfsvariablen so gesetzt wie es in der Induktionsbasis beschrieben ist. Was das bedeutet steht weiter oben bei der Invariante.

Erklär doch nochmal genau das Problem. :)

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Pivot partitioning by scanning

Beitrag von AnnaW »

*Kopf -> Tisch* ja ich habe meinen Denkfehler. Mal wieder komplizierter gedacht als es eigentlich ist... Damit ist \(m_2 = 6\)

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Pivot partitioning by scanning

Beitrag von AnnaW »

Danke schön :-)

Benutzeravatar
Capricorn
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 29. Apr 2013 12:12

Re: Pivot partitioning by scanning

Beitrag von Capricorn »

Hi,

noch eine allgemeinere Frage zum "Pivot partitioning by scanning". Heute im Theorietestat habe ich erwähnt, dass es Ähnlichkeit mit Quicksort hat (Pivot-Elemente, Unterteilen der Eingabe in alles kleiner, alles gleich und alles größer dem Pivotwert) und somit eine Art "Quicksort in-place"-Variante ist.
Der Reaktion des Tutors nach ist dies jedoch falsch... Habe ich da etwas missverstanden?

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Pivot partitioning by scanning

Beitrag von robertH »

Meines Erachtens ist es so:
Quicksort ist ein Algorithmus zum Sortieren, in dem im 1. Schritt Pivot partitioning angewendet wird um die 3 Teillisten zu erhalten. Dementsprechend wendet Quicksort-in-place pivot partitioning by scanning (oder einen anderen Algorithmus der in-place die Teillisten erzeugen kann) an. Eine Sortierung, rekursive Aufrufe etc. kommen im pivot partitioning jedoch nicht vor, weshalb es nicht so eine Art quicksort ist.

Antworten

Zurück zu „Archiv“