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;
  }

}

TechnikSpezi

28.11.2021, 18:06

Bitte den Code anständig formatieren (nutz die Funktion für Quellcode), damit er lesbarer wird.

Soroushsaberi

Fragesteller

28.11.2021, 18:12

Ich habe es eingefügt :)

2 Antworten

heizfeld

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Technik

28.11.2021, 18:20

Hallo,

das ist einfach noch sehr unleserlich, daher wird in der Informatik der leicht verständliche Preudocode verwendet.

Quicksort ist ein rekursiver Algorithmus, das heisst er ruft sich selbst immer wieder auf, bis ein Array von n Elementen vollständig sortiert vorliegt. Das ist der Fall wenn links vom untersuchten Element kein größeres und rechts davon kein kleineres mehr vorhanden ist. Gestartet wird die Suche etwa in der Mitte der Elemente.

Zunächst die rekursive Prozedur. Man beachte den Selbstaufruf in dieser!

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler - 1)
         quicksort(teiler + 1, rechts)
     ende
 ende

Die folgende Implementierung der Funktion

teile

teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen:

 funktion teile(links, rechts)
     i := links
     // Starte mit j links vom Pivotelement
     j := rechts - 1
     pivot := daten[rechts]

     wiederhole solange i < j // solange i an j nicht vorbeigelaufen ist 
         // Suche von links ein Element, welches größer oder gleich dem Pivotelement ist
         wiederhole solange i < rechts und daten[i] < pivot
             i := i + 1
         ende

         // Suche von rechts ein Element, welches kleiner als das Pivotelement ist
         wiederhole solange j > links und daten[j] >= pivot
             j := j - 1
         ende

         falls i < j dann
             tausche daten[i] mit daten[j]
         ende
     ende
    

     // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
     // und gib die neue Position des Pivotelements zurück, beende Durchlauf
     falls daten[i] > pivot dann
         tausche daten[i] mit daten[rechts]
     ende
     antworte i
 ende

Quelle des Pseudocodebeispiels: Wikipedia

Harry

Soroushsaberi

Fragesteller

28.11.2021, 19:41

Vielen vielen Dank für Ihren Erklärung <3

Palladin007

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Technik, programmieren

28.11.2021, 19:41

Quicksort – Wikipedia

Da wird's erklärt.

Ähnliche Fragen

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zur Frage

wie kann ich durch einen baum iterieren Java?

package ListenInJava.Baume;


public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;


    TreeNode(int data){
        this.data = data;
        this.left = null;
        this.left = null;
    }
}





package ListenInJava.Baume;


public class Tree {
    TreeNode root;


    Tree (){
        root = null;
    }


    public void add(int data){
        TreeNode t1 = new TreeNode(data);
        if(root == null){
            root = t1; 
            return;
        }
        TreeNode help = root;
        while(help != null){
            if(help.data > t1.data){
                
                if(help.left == null){
                    help.left = t1;
                    return;
                }
                help = help.left;
            } else{
                if(help.right == null){
                    help.right = t1;
                    return;
                }
              help = help.right;   
            }
        }
        return;
    }


 
}

ich möchte dann den baum in form von:

root

left right

usw. haben, aber wie genau könnte ich denn durch den baum iterieren mit einer schleife?

...zur Frage

Wie kann ich in C# mit Pfeiltasten die Cursor-Position verändern?

Guten Tag,

ich will, dass, wenn ich in einer Konsolenanwendung die jeweiligen Pfeiltasten drücke, sich dann auch die Cursor-Position ändert.

Ich habe es gerade so:

Console.SetWindowSize(80, 24);
Console.SetBufferSize(80, 24);
Console.SetCursorPosition(0, 0);
Console.Clear();

int down = 0;
int up = 0;
int left = 0;
int right = 0;

do
{
  ConsoleKeyInfo Taste;
  Taste = Console.ReadKey(false);

  if (Taste.Key == ConsoleKey.DownArrow)
  {
    do
    {
      down++;
      Console.SetCursorPosition(0, down);
    }
    while (true == false);
  }

  if (Taste.Key == ConsoleKey.UpArrow)
  {
    do
    {
      up--;
      Console.SetCursorPosition(0, up);
    }
    while (true == false);
  }

  if (Taste.Key == ConsoleKey.RightArrow)
  {
    do
    {
      right++;
      Console.SetCursorPosition(right, 0);
    }
    while (true == false);
  }

  if (Taste.Key == ConsoleKey.LeftArrow)
  {
    do
    {
      left--;
      Console.SetCursorPosition(left, 0);
    }
    while (true == false);
  }
}
while (true == true);

Das Problem aber ist: Wenn ich nach unten gehe und dann nach rechts gehen will, dass der Cursor wieder an den Anfang springt.

Was auch nicht funktioniert ist: Wenn ich nach links oder nach oben gehen will. Weil das -- nicht so funktioniert, wie es soll.

...zur Frage

In Java bestimmte Werte aus einem Array in Indexvariable eines neuen Arrays speichern?

Hallo,

ich habe gerade das Problem, dass ich an einer Aufgabe sitze, bei welcher man ein Neues Feld erzeugen soll in welchem die Werte aus einem vorgegebenen Feld so eingefügt werden, dass alle negativen Zahlen im linken Bereich und alle postiven Zahlen sowie 0 im rechten Bereich liegen. Gegeben ist folgender Code:

public static int randomInt(int a, int e) {
    return (int) (Math.random() * ((e - a) + 1)) + a;
}

public static void fuellen(int[] feld, int a, int e) {
    for (int i=0;i<feld.length;i++){
        feld[i] = randomInt(a,e);
    }
}

public static void ausgeben(int[] feld){
    for (int i=0;i<feld.length;i++){
        System.out.printf("%3d ", feld[i]);
        if ((i+1) % 10 == 0) {
            System.out.println();
        }
    }
    System.out.println();
}

bis Jetzt war mein Ansatz dieser hier:

public static int[] verteilen(int[] feld){
    int[] feld2 = new int[feld.length];
    int first = feld2[0];
    int last = feld2[feld2.length - 1];
    int count = 0;
    int right = feld2.length - 1;
    for(int i=0;i<feld.length;i++) {
        if(feld[i] < 0) {
            first = feld[i];
            count++;
        }
        else {
            last = feld[i];
            right--;
        }
    }
    return feld2;
}

und als Ergebnis soll das rauskommen aber irgendwie klappt es nicht:

39-34 76-84-79-61-59-50 96 55 -71-51-89 77 64 93-20-86 43 33

-34 -84 -79 -61 -59 -50 -71 -51 -89 -20
-86  33  43  93  64  77  55  96  76  39

...zur Frage

Java: Methode wird sehr wahrscheinlich nicht aufgerufen?

Mein Programm lässt sich ohne jegliche Fehlermeldungen, etc. kompilieren und ausführen. Beim Ausführen des Codes stoppt es ohne einen von mir ersichtlichen Grund, wenn es die Methode karteout() ausführen soll. Es zeigt mir, wo es eigentlich einen Namen einer Spielkarte anzeigen sollte, einfach eine leere Zeile an, in die ich nichts eingeben kann.

Mein Code:

Main.java:

public class Main {
  public static void main(String[] args) {
    Kartendeck karten = new Kartendeck();
    karten.kartendeck();
    Player pturn = new Player();
    pturn.player();
  }
}

Kartendeck.java:

import java.util.Random;

public class Kartendeck {
  private int counter1;
  private int cardid;
  private int[] cards = new int[52];
  private int karte;
  private int zs1;

  public void kartendeck() {
    counter1 = -1;

    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 13; j++) {
        i++;
        j++;
        cardid = 100 * i + j;
        counter1++;
        i--;
        j--;
        cards[counter1] = cardid;
      }
    }
  }

  public void karteout() {
    Random random = new Random();
    loopkarte: while (true) {
      karte = random.nextInt(52);
      zs1 = cards[karte];

      if (cards[karte] != 0) {
        cards[karte] = 0;
        break loopkarte;
      }
    }

    if (zs1 % 100 == 1) {
      System.out.print("Ace ");
    }
    else if (zs1 % 100 == 2) {
      System.out.print("2 ");
    }
    else if (zs1 % 100 == 3) {
      System.out.print("3 ");
    }
    else if (zs1 % 100 == 4) {
      System.out.print("4 ");
    }
    else if (zs1 % 100 == 5) {
      System.out.print("5 ");
    }
    else if (zs1 % 100 == 6) {
      System.out.print("6 ");
    }
    else if (zs1 % 100 == 7) {
      System.out.print("7 ");
    }
    else if (zs1 % 100 == 8) {
      System.out.print("8 ");
    }
    else if (zs1 % 100 == 9) {
      System.out.print("9 ");
    }
    else if (zs1 % 100 == 10) {
      System.out.print("10 ");
    }
    else if (zs1 % 100 == 11) {
      System.out.print("Jack ");
    }
    else if (zs1 % 100 == 12) {
      System.out.print("Queen ");
    }
    else if (zs1 % 100 == 13) {
      System.out.print("King ");
    }
    else {
      System.out.print("");
    }

    if ((zs1 - zs1 % 100) / 100 == 1) {
      System.out.println("of Spades");
    }
    else if ((zs1 - zs1 % 100) / 100 == 2) {
      System.out.println("of Hearts");
    }
    else if ((zs1 - zs1 % 100) / 100 == 3) {
      System.out.println("of Clubs");
    }
    else if ((zs1 - zs1 % 100) / 100 == 4) {
      System.out.println("of Diamonds");
    }
    else {
      System.out.print("");
    }
  }
}

Player.java:

import java.util.Scanner;

public class Player {
  private String userinput;

  public void player() {
    Scanner scan = new Scanner(System.in);
    Kartendeck karten = new Kartendeck();
    System.out.println("CPU's up:");
    karten.karteout();
    System.out.println("Deine Startkarten:");
    karten.karteout();
    karten.karteout();

    loopturn: while (true) {
      System.out.println("Was möchtest du machen?");
      System.out.println("--> Hit");
      System.out.println("--> Stay");
      userinput = scan.nextLine();

      loopuser: while (true) {
        if (userinput.equals("Hit")) {
          karten.karteout();
          break loopuser;
        }
        else if (userinput.equals("Stay")) {
          break loopturn;
        }
        else {
          System.out.println("Diese Funktion ist nicht verfügbar!");
        }
      }
    }
  }
}

Ich hoffe, mir kann jemand helfen und vielen Dank im Voraus.

...zur Frage

Fehler im Code?

Hey Leute,

Mir wird im Code andauern der gleiche Fehler rausgeschmissen, kann mir da wer helfen?

Hier der Code:

import java.util.Random;

public class aufgabe14 {
    public static void main(String[] args) {
        Random rand = new Random();
        int target = rand.nextInt(100) + 1;
        int count = 0;
        int maxTries = 10;
        int guess;
        System.out.println("Rate eine Nummer zwischen 1 und 100!");

        do {
            guess = Integer.parseInt(System.console().readLine());
            count++;
            if (guess > target) {
                System.out.println("Du hast zu hoch geraten!");
            } else if (guess < target) {
                System.out.println("Du hast zu niedrig geraten!");
            }
        } while (guess != target && count < maxTries);

        if (guess == target) {
            System.out.println("Du hast die nummer in " + count + " versuchen erraten!");
        } else {
            System.out.println("Du hast versagt die nummer in  " + maxTries + " versuche zu erraten!");
        }
    }
}

...zur Frage

Wie bekomme ich eine Kollisionsbehandlung hin?

Hi Leute :) Ich bin dabei ein kleines Jump&Run in Java zu programmieren und bin nun schon seit geraumer Zeit an der Kollisionsauflösung hängengeblieben. Die Erkennung von Kollisionen habe ich bereits gelöst. Ich habe nun schon das halbe Internet abgesucht, bin aber nicht schlauer geworden. Könnt ihr mir helfen? Ich habe bisher eine HALBWEGS funktionierende Kollisionserkennung hinbekommen.

Gegeben sind mir: -Position des Spielers(px, py), -Größe des Spielers(playerSize), -Pos. der Hitbox(bx, by), -Seitenlänge der Hitbox(boxSize), -Bewegungsrichtung des Spielers(movex, movey), -Zielposition des Spielers ohne Einbezug der Kollision(destx, desty), -Geschwindigkeit des Spielers(vel) --- alles vom Typ "int"

Das Problem: so wie ich das gelöst habe ist die Auflösung fehlerhaft. Wenn ich geradewegs auf die Hitbox zukomme mit einer Geschwindigkeit von z.B. 5 Pixel pro Frame und ich rage bei der Kollision so in die Hitbox hinein, dass der x-Anteil größer ist als der y-Anteil, dann wird es nach y aufgelöst.

Ich wollte in jedem Schleifendurchlauf die Kollision mit allen überlappenden Tiles so auflösen: Mein bisheriger Code:

if(intersect(...)){ //wenn die Kollision mit der aktuellen Box feststeht
int tilex = bx
int tiley = by
                    
int yover = desty + playerSize - by;        //positiv wenn überlappung
int yunder = by + boxSize - desty;      //positiv wenn überlappung
int xleft = xdest + playerSize - bx;        //positiv wenn überlappung
int xright = bx + boxSize- destx;       //positiv wenn überlappung
                    
boolean left = false, right = false, top = false, bottom = false;  

//Überragt der Spieler die obere, untere, linke oder Rechte Seite der Box 
                    
if(desty < by) top = true;
if(desty + playerSize > by + boxSize) bottom = true;
if(destx < bx) left = true;
if(destx + playerSize > bx + boxSize) right = true;
                    
if(top && !right && !left) desty = by - playerSize;
if(bottom && !right && !left) desty = by + boxSize;
if(left && !top && !bottom) destx = bx - playerSize;
if(right && !top && !bottom) destx = bx + boxSize;
                    
if(top && right){
    if(yover < xright) desty = by - playerSize;
    if(yover > xright) destx = tilex + boxSize;
}
if(top && left){
    if(yover < xleft) desty = by - playerSize;
    if(yover > xleft) destx = bx - playerSize;
}
if(bottom && left){
    if(yunder < xleft) desty = by + boxSize;
    if(yunder > xleft) destx = bx - playerSize;
}
if(bottom && right){
    if(yunder < xright) desty = by + boxSize;
    if(yunder > xright) destx = bx + boxSize;
}
}

Meine Frage ist nun: Wie bekomme ich so eine realistische und genaue Kollisionsbehandlung hin (mit destx und desty als Zielpositionen)? Es geht mir dabei nicht um einwandfreies Java, es zählt nur die Logik dahinter (von mir aus auch Pseudo-code).

Vielen Dank im Voraus :)

...zur Frage

Struktogramm zu Code umformen?

Wie konvertiere ich folgendes Struktogramm (https://prnt.sc/qysvkl)?

Code:

/** bestimmt Ziffer Verpackungsart
  * @param pErsterBuchstabeArt erster Buchstabe der Verpackungsart
  */
public void bestimmeZifferVerpackungsart(char pErsterBuchstabeArt) {
  char [] alphabet = { 'T', 'F', 'K', 'B', 'S', 'V', 'D' };
  String s;
  s = new String(alphabet);
  boolean gefunden = false;
  int i = 0;

  while (gefunden = false) {
    if (pErsterBuchstabeArt = s.contains() = true) {
      zifferVerpackungsart = i + 1;
      gefunden = true;
      i++;
    }
  }
}

...zur Frage

Elemente in Arrays (java) einfügen?

Hallo! Hier habe ich ein bisschen mit Arrays rumgespielt. Es soll eine 0 in das kopierte Array vor der jeweiligen Zahl eingesetzt werden, wenn diese kleiner als 10 ist. Wenn die Zahl größer als 10 ist, dann wird eine 1 vor die jeweilige Zahl gesetzt.

Wäre so ein Lösungsansatz akzeptabel oder haben sich Fehler eingeschlichen?

Muss dazu sagen, dass ich ein Anfänger bin :)

Danke im Vorraus!

Der Code lautet:

public class Array {
    public static void main (String[] args){
       Array arrayListe = new Array();
       int[] liste = {5, 20, -9};
       int[] rueckgabe = Array.veraendereArray[liste];
       for(int element : rueckgabe){
       System.out.println(element);
    }
 }
public static int [] veraendereArray(int[] liste){
   int[] rueckgabe = new int[liste.length+4];
   for(int i = 0; i <= liste.length; i++){
      if(element <10){
         rueckgabe[i+1]=0;
      }
      else{
         rueckgabe[i+1] =1;
      }
   }
}
 }

...zur Frage

Handy-Code "knacken" ?

Hallo,

Die Frage steht ja bereits oben. Kann ich nicht einfach ein Programm in Java machen, welches mit einfachen if,else und while Strukturen ein Passwort herausfindet ?

package com.company.HandyCodeKnacker;
import java.util.*;

public class Main {

    public static void main(String[] args) throws InterruptedException {
        int Code = (int) (Math.random() * 10000);
        int Versuche = 0;
        int Zufall = (int) (Math.random() * 10000);

        System.out.println("Generiere zufälligen Code : ...");
        System.out.println("Dein Code ist : " + Code);
        System.out.println("Es wird versucht deinen Code zu finden...");
        Thread.sleep(2000);
        while (Zufall != Code) {
            Zufall = (int) (Math.random() * 10000);
            System.out.println(Zufall);

            if (Zufall == Code) {
                System.out.println("Dein Code ist : " + Zufall);
                System.out.println("Ich habe " + Versuche + " Versuche gebraucht.");
            }
            Versuche++;
        }



    }

}

Das müsste doch gehen, oder ? Das müsste man nur in einer Datei verpacken, dann auf dem Handy öffnen und der Code steht da, oder geht das nicht?

...zur Frage

Java Arrays?

Wir haben die Aufgabe bekommen dieses Programm umzuschreiben, sodass keine Schleifen vorkommen nur if, if else und else if. Sprich er soll sortieren aber nur mit den if abfragen.

Wir sollen Aufgabe 1 a) machen wie es oben in dem Bild geschrieben ist

public class Main
{
    public static void main(String[] args)
    {
        //Array deklarieren und initialisieren
        int[] array=new int[]{3,1,2};

        //Array sortieren
        for (int j=0; j<array.length-1;j++)
        {

            for (int i=0;i<array.length-1-j;i++)
            {

                //falls linkes Element größer > tauscht mit rechts
                if(array[i]>array[i+1])
                {
                    //tauschen
                    int memory=array[i];
                    array[i]=array[i+1];
                    array[i+1]=memory;
                }
            }
        }

        //Array ausgeben
        System.out.println("Anzahl der Schritte: ");


        //zählt die einzelnen zahlen bis er durch ist
        for(int i=0;i < array.length;i++)
        {
            System.out.print(array[i]+" ");
        }
    }

...zur Frage

Fakultät-Rechner in Java programmieren?

Ich habe folgendes Programm:

public class test {
    public static void main(String[] args) {
      System.out.println(fakulteat(5));
    }
    
    public static int fakulteat(int zahl) {
      if (zahl == 1) {
        return 1;
      } else {
        return zahl * fakulteat(zahl - 1);
      }
    }
}

Hier wird jetzt ja die Fakultät berechnet durch diese rekursive Methode.

Mein Problem steckt folgender Zeile:

return zahl * fakulteat(zahl - 1);

Damit gibt man dann so gesagt " 5 * 4! " an die Methode zurück.

Was ich mich aber Frage ist halt, wieso " fakulteat(zahl - 1) " jetzt eine Fakultät darstellt. Der Methode gibt sich selbst damit doch nur einen Wert zurück, woher weiß aber die Methode, dass dann z.B. 4! = 1 * 2 * 3 * 4 gemeint ist?

...zur Frage

BlueJ Methode für eine private Nachricht?

Hier ist der Code, ich brauche eine Methode mit der ich eine Nachricht an einen User an einen Server senden kann der nur dieser User sieht

public class EchoServer extends Server {

public EchoServer(int port) {

super(port);

System.out.println("Der DBG-ECHO-Server hat die IP " + getIP() + " und lauscht auf Port " + port + "!");

}

public void processNewConnection(String pClientIP, int pClientPort) {

System.out.println("Neue Verbindung von " + pClientIP + " : " + pClientPort + ".");

send(pClientIP, pClientPort, "Herzlich willkommen beim DBG-ECHO-Server, Quit um abzumelden, Everybody für Message an alle");

}

public void processMessage(String pClientIP, int pClientPort, String pMessage) {

if (pMessage.equals("Quit")) {

closeConnection(pClientIP, pClientPort);

}

if (pMessage.substring(0, 9).equals("Everybody")) {

sendToAll(pMessage);

}

System.out.println("Server hat Nachricht \"" + pMessage + "\" vom Client " + pClientIP + ":" + pClientPort + " empfangen.");

send(pClientIP, pClientPort, "Antwort vom DBG-ECHO-Server: Deine Nachricht lautete \"" + pMessage + "\".");

System.out.println("Server hat Nachricht \"" + pMessage + "\" an Client " + pClientIP + ":" + pClientPort + " zurückgesendet.");

//sendToAll(pMessage);

//closeConnection(pClientIP, pClientPort);

}

public void processClosingConnection(String pClientIP, int pClientPort) {

}

public void privateMessage(String pClientIP, int pClientPort, String pMessage) {

if (pMessage.substring(0, 9).equals(pClientIP)) {

System.out.println("User schrieb

send(pMessage);

}

public String getIP() {

try {

String ipAdresse = "" + InetAddress.getLocalHost();

String[] hostUndIP = ipAdresse.split("/");

String adressat = hostUndIP[0].trim();

ipAdresse = hostUndIP[1];

return ipAdresse;

}

catch (UnknownHostException e) {

e.printStackTrace();

...zur Frage

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?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen