Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

1 Antwort

Vom Beitragsersteller als hilfreich ausgezeichnet

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren, Informatik

26.10.2019, 01:09

Es gibt verschiedene Quicksorts - zum Stack greift man bei nicht rekursiver Variante. Swaps macht man allgemein bei Sortierung inplace.

Soweit so gut erstmal.

Im besten Fall teilt Dein Pivot die Eingabemenge beim Paritionieren in zwei gleich große Teilarrays, das sichert Dir die minimale Rekursionstiefe zu. (kürzeste Laufzeit).

----

Du sollst jetzt im Prinzip die Wahrscheinlichkeit dafür berechnen, daß Deine Pivotwahl einen Split erzeugt, der nicht schlechter als 1/4 zu 3/4 ist, heißt das größere Array soll nicht größer als 3/4 der Elemente sein, das kleinere nicht kleiner als 1/4 der Elemente.

Das ist also ein rein stochastische Ding - Ziehe ich uniform ein Element, beträgt die Wahrscheinlichkeit dafür, daß es zwischen 1/4 und 3/4 liegt 0.5. Das gilt auch für jedes der 7 Elemente jeweils. Jetzt bleibt die Frage, wie groß ist die Wahrscheinlichkeit, daß genau das 4. kleinste der 7 im gewünschten Intervall ist? (Also im Prinzip das mittlere)

-----

⌈(links+rechts)/2⌉ - es sei links =n und rechts = n+6 - eien Folge der Länge 7. es ist n+n+6=(2n+6)/2=n+3- also das 4. und somit mittlere Element der Folge.

dort packst Du natürlich das kleinste aller Elemente hin (oder das größte, denn dann entsteht beim pivotieren ein Array der Größe n-1 sowie ein leeres.

KarlRanseierIII

26.10.2019, 01:23

 0   1   2  3  4   5   6

n+6 n+4 n+2 n n+1 n+3 n+5

Natürlich muß das nicht n +1, n+2 usw. sein, sondern es reicht, wenn die Ordnung gewahrt bleibt, also Mitte kleinste Element, rechts daneben das zweitkleinste, dann links das drittkleinste usw. .

Natürlich klappt es genauso gut, wenn das größte, das zweitgrößte ... genommen wird.

Der Grund für die Anordnung ist ceil(), also das Aufrunden.

KarlRanseierIII

26.10.2019, 02:58

@KarlRanseierIII

Nochmal zu 1 a) ein Gedanke:

Das mittlere der 7 Elemente liegt genau dann im Intervall, wenn nicht 4 oder mehr Elemente unterhalb des Intervalls liegen, oder wenn nicht 4 oder mehr Elemente oberhalb des Intervalls liegen.

Jensek81

Beitragsersteller

27.10.2019, 16:08

@KarlRanseierIII

Danke für die Antwort KarlRansereiIII.

Eine Frage noch zur 1a).

Wenn ich dich richtig versteh, gibt es also 3 zu betrachtende Intervalle bei reinzufälliger Wahl eines Elements

1) Element ist kleiner als Intervall (0, 1/4)

2) Element liegt genau dazwischen ((1/4 + 1), 3/4)

3) Element ist größer als Intervall (3/4, n)

Wir betrachten nun, dass 4 oder mehr Intervalle oberhalb des Intervalls liegen, d.h.

k = 4,5,6,7.

Könnte man dann nicht einfach die Binominalverteilung über dieses Ereignisse bilden, aufsummieren und die Gegenwahrscheinlichkeit bilden.

D.h. (n über k) * p^k * (1 - p)^n-k ? aufsummiert für k = 4 bis 7?

Weil wir den Hinweis bekommen haben, P (falsches Intervall) und P (beide im falschen Intervall) zu berechnen. Die gesuchte Lösung wäre dann 1 - P (Beide im falschen Intervall). Mich verwirrt dieses beide im falschen Intervall. Warum beide? Wir wählen doch nur ein zufälliges Element.

KarlRanseierIII

27.10.2019, 16:35

@Jensek81

Ja, mir war heute morgen nachm Aufstehen auch noch etwas dazu durch den Kopf gegangen ...

Es fühlt sich definitiv binomial an, das wäre auch die Richtung in die ich gehen würde. Die Frage ist halt genau das richtige zu ermitteln.

gehen wir es mal durch: Es können 6 von sieben außerhalb unseres mittleren Intervalls liegen, das mittlere Element könnte aber immernoch im Intervall oder außerhalb liegen.

Wenn meine Elemente aber sortiert sind und ich das 4. ziehe, aber mindestens 4 Elemente unterhalb von 1/4 n liegen, dann weiß ich, daß mein gezogenes Element außerhalb meines Wunschintervalls liegt. Ebenso bezüglich des anderen Intervalls (also oberhalb).

Wenn ich jetzt aber von dieser (jeweiligen) Wahrscheinlichkeit die Gegenwahrscheinlichkeit bilde, wäre das aber nicht mehr auf mein Wunschintervall beschränkt. (Ich will ja schließlich Element 4 liegt nich oberhalb und nicht unterhalb).

Ich frage mich was mit:

P (beide im falschen Intervall)

gemeint sein soll.

Jensek81

Beitragsersteller

27.10.2019, 16:49

@KarlRanseierIII

Vielleicht, wenn man beide Seiten getrennt betrachtet. Also einmal das Szenario dass die kleinsten 4 in das größte Intervall fallen, oder den ungekehrten Fal, dass die 4 größten in das kleinste Intervall fallen.

Unser Tutor hat uns zudem verraten, dass die Lösung wohl 85,88 % sein soll.

Darauf würde ich mit der binominalverteilung auch kommen, d.h.

Summe von k = 4 bis 7: (7 über k) * 1/4^k * 3/4^(7-k) = 0,0706

Jetzt dieser komische Zwischenschritt, den ich nicht verstehe:

2 * 0,0706 = 0,1412

Naja, und dann eben über die Gegenwahrscheinlichkeit: 1 - 0,1412 = 85,88 %

Diese 2 * 0,0706 ("Beide im falschen Intervall") verwirrt mich. :/

KarlRanseierIII

27.10.2019, 17:03

@Jensek81

Also, nochmal:

Wenn mindestens 4 Elemente von 7 unterhalb 1/4 n liegen, dann liegt das mittlere der 7 unterhalb des Intervalls, in dem liegen sollte, wenn alles gut ist.

Das ist, ohne es jetzt gegenzurechnen laut Deiner Aussage: 0.0706.

Oder aber 4 oder mehr Elemente liegen Oberhalb 3/4, das ist nun ebenso 0.0706.

Die Wahrscheinlichkeit, daß also das eine ungünstige Ereignis eintritt, ODER das andere wäre die Summe, also 2*0.0706. Die Gegenwahrscheinlichkeit, also 1-2*0.0706 wäre demnach die Wahrscheinlichkeit für unseren günstigen Fall.

Beide ungünstigen Fälle sind disjunkt - das ist wichtig.

Jensek81

Beitragsersteller

27.10.2019, 17:07

@KarlRanseierIII

Ok vielen Dank, KarlRansereiIII. Das war genau das, was mir bisher unklar war. EInen schönen Abend noch :)

Ähnliche Beiträge

Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

...zum Beitrag

Quicksort "Code" erklären?

Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) return;

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}

...zum Beitrag

wann ist quicksort langsamer als bubblesort - Beispiel?

hey ich möchte gerne mal ein Zahlenfolge-Beispiel sehen, wo man das genau sieht. habe schon viele zahlenfolgen gemacht wo die Liste bereits aufsteigend sortiert ist und wo das element das pivotelement ist ;D

Danke im voraus

...zum Beitrag

Quicksort Algorithmus, Hilfe?

Irgendwie machen das alle anders. An meiner Uni wird das so gemacht:

Ich verstehe das nicht. Wenn die Zeiger übereinander laufen, dann kommt bei mir eine andere Zahlenfolge raus, als auf dem Bild. Außerdem weiß ich nicht, wie das Pivot in der Mitte platziert wurde.

Kann mir jemand bitte Schritt für Schritt erklären, wie hier gearbeitet wurde? Ich wäre so dankbar.

...zum Beitrag

Array im Pseudocode?

Leider habe ich Probleme zu verstehen was dieser Algorithmus genau macht, bzw was im roten Kasten als Lösung kommt.

Soweit ich verstehe beginne ich beim ersten Element von b und gehen dann bis zum 2 (3-1=2). Diese Elemente vergleiche ich mit den Elementen in a. In diesem Fall kommen beide (0 und 3) mehrfach in a vor. Da liegt auch mein Verständnis Problem. Der Algorithmus setzt dann den Wert von c am Index i (also 0 und 1) auf c.get(i)+1. Damit kann ich leider nichts anfangen.

c.get(i) liest das Element an dieser Index Position aus. Aber was ist das für diesen Fall?

Vielen Dank schonmal für eure Hilfe!

...zum Beitrag

Numpy Array Frage?

Bei ca. 600 Datensätzen wird sich das schon lohnen.

Alles sind floats

so nun will ich, effizient, etwas schieben

Konkret: Ich will am Array ein Element hinten anhängen und das erste Element löschen, also so löschen, dass der erste Platz gar nicht mehr da ist. Und das nullte Element somit mein ursprünglich zweites Element ist.

Evtl. könnte ich, wenn ich das neue Element hinten angehängt habe, alle Elemente eins nach links schieben, damit der erste Platz wieder belegt ist.

Geht das irgendwie möglichst effizient?

...zum Beitrag

Python Pivot Element Suche?

Hallo,

ich hänge an folgender Aufgabe fest:

Ich soll in Python eine Funktion schreiben, welche eine Matrix und einen Spaltenindex übergeben bekommt und den Zeilenindex des betragsmäßig größten Elements aus dieser Spalte zurückgibt.

Hierbei soll der zurückgegebene Zeilenindex immer größer oder gleich dem Spaltenindex sein.

Vielleicht kennt sich ja jemand gut aus und kann mir etwas Hilfestellung geben, ich bin für jede Hilfe dankbar :)

Viele Grüße,

bamu

...zum Beitrag

Java Bubble Sort Algorithmus programmieren wer kann mir helfen (bitte keine Lösung schreiben sondern nur Tipps geben)?

Die Aufgabenstellung lautet:

"Damit Sie sehen wie nervig das Sortieren eines Arrays wirklich sein kann wenn man es selbst programmieren muss: implementieren Sie einen einfachen Sortieralgorithmus in einer Methode namens 'bubblesort'. Diese Methode erwartet einen Parameter 'x' wie in der letzten Aufgabe, und verfährt auch genauso mit ihm. Die Sortierung wird wie folgt durchgeführt: angefangen beim zweiten Array-Element (also mit Index 1) prüfen Sie für alle Elemente, ob sie kleiner sind als ihr Vorgänger, und vertauschen sie sofort falls ja. Dies wird so lange durchgeführt, bis bei einem kompletten Durchlauf durch das Array (beginnend bei Index 1) keine Vertauschung mehr vorgenommen werden muss, in diesem Fall ist das Array sortiert. Falls das Array 0 oder 1 Elemente hat muss nichts getan werden da solche Arrays bereits sortiert sind (warum?). Tipp: die perfekte Gelegenheit eine do/while-Schleife zu benutzen!"

Mit freundlichen Grüßen

...zum Beitrag

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zum Beitrag

JavaScript programmieren Ausgaben alert Informatik?

Es geht um die b)

Weis jemand wie man hier vorgeht? Ich versteh das mit dem alert 4,5,6 nicht. Das array hat doch nichtmal so viele Elemente.

Aufgabe steht links und Lösung Rechts. Aufgabe: was gibt das JavaScript Programm aus?

...zum Beitrag

Power Point (Open Office) - Objekt soll von links nach rechts

Hallo, wie mach ichs, das das Objekt von links nach rechts sich "bewegt" und dann rechts verschwindet? habe das Power Point von Open Office

...zum Beitrag

Wie ist diese Aufgabe zu lösen?

Hey, hab eine Aufgaben von denen ich keine Ahnung hab wie ich diese lösen kann. Hab die Erfahrung gemacht nachdem man den Code sieht, die Lösung einem absolut einleuchtet. Nur komm ich grad mit nur googlen und tutorials nicht weiter. Wäre super wenn mir hier einer helfen kann.

Aufgabe :

Schreiben Sie eine Methode public static String []reverse(String[]stringArray).

Diese Methode erzeugt ein neues String-Array. Dieses enthält die Werte des übergebenen Arrays in umgekehrter Reihenfolge. Das erste Element ist zwei Mal enthalten. Eine Referenz auf dieses Array wird zurückgegeben.

Beachte : Der Wert der globalen Variablen stringArray bleibt unverändert.

Bsp: Wenn das übergebene Array [Max,Mustermann] enthält wird eine Referenz auf das Array [Mustermann,Mustermann,Max] zurückgeben.

Hoffe einer kann mir helfen danke !

...zum Beitrag

Kann mir jemand folgenden Code erklären?

Hallo Leute,

in der Schule habe ich die Aufgabe bekomme, aus einer Liste, das größte und zweit größte Element raus zu picken. Im Internet habe ich hierfür eine Lösung gefunden, die funktioniert. Doch verstehen tu ich die Lösung nicht hundert Prozent. Ich verstehe nicht wie max und secondmax die Werte bekommen und die einzelnen Werte aus der Liste gefiltert werden.

// Ausgabe 3
int[]array={3,1,5,7,4,12,3,8,-2};


// Ausgabe 3
public static void sortiereElement(int[] array){
    int max = 0;
    int secondmax = 0;

    for(int i=0; i<array.length; i++){
        if(array[i] > max){
            secondmax = max;
            max = array[i];
        }else if(array[i] > secondmax){
            secondmax = array[i];
        }
    }

    // Ausgabe
    System.out.print("Aufgabe 3:" + "\t" + "\n");
    System.out.print("Größtes Element: " + max + "\t" + "\n");
    System.out.print("Zweitgrößtes Element: " + secondmax + "\t" + "\n");

}

--------------------------------------------------------------------
Ausgabe:
Aufgabe 3:	
Größtes Element: 12	
Zweitgrößtes Element: 8

...zum Beitrag

Warum sollte man Lineare Listen (arrays) als Datenstruktur verwenden?

Lineare Listen haben erstmal sehr viele Nachteile...

Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.

Dagegen sind Bäume:

Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
Suche funktioniert aufbaubedingt IMMER in O(log(n))
Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).

Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen