Die Zahl in der Mitte finden

[deggit_biber]

Hallo,
ich stehe gerade etwas auf dem Schlauch. Vielleicht könnt ihr mir ja schnell weiterhelfen?
Ich habe drei Int-Variablen die in jeden Durchlauf einen anderen Int-Wert bekommen. Jetzt würde ich gerne wissen, welche dieser drei Variablen jeweils den Wert hat, der in der Mitte ist.

Ein kleines Beispiel
Durchlauf1:
z1=30
z2=70
z3=10
Rückgabe z3

Durchlauf2:
z1=6
z2=8
z3=2
Rückgabe z1

Könnte das so klappen?

    private int Mitte (int z1, int z2, int z3)
    {
        if (z1>z2 && z1<z3)
        {
            return z1
        }
    }

vielen lieben Dank für die Hilfe
Deggit

 

[Robat]

Durchlauf1:
z1=30
z2=70
z3=10
Rückgabe z3

Ich war nie der Beste in Mathe aber ich bin mir ziemlich sicher, dass das z1 sein müsste!

Könnte das so klappen?

Das schöne an der Programmierung ist doch, das man ausprobieren kann.
Mach das doch einfach mal

Wenn ein Fehler kommt sind wir gerne für dich da!

Try & Error ist mMn der schönste Weg zu lernen

 

[Schmetterhand]

Könnte das so klappen?

Eine der besten Aussagen, die ich je von einem Programmierer gehört habe!
Zum Problem: Das geht mit einfacher Logik (diese eine Bedingung in Deiner if-Abfrage genügt nicht, schließlich hast Du drei Fälle ), aber diese umzusetzen solltest Du selber können, ohne hier das Forum zu bemühen...

 

[deggit_biber]

Ja ihr habt recht, war gestern schon spät und ich hab nicht richtig nachgedacht.

Das mit dem mittleren Element auswählen klappt jetzt auch. (habe es mit Int-Werten in einer separaten Methode einmal durchgeführt).

Leider habe ich jetzt ein anderes Problem und hier bräuchte ich wirklich eure Hilfe.

Konkret geht es um die Auswahl des Pivot-Elementes im QuickSort. Ich möchte drei random Elemente aus dem noch zu sortierenden Array auswählen und dann das mit dem mittleren Int-Wert zum pivot bestimmen.

Leider bekomme ich in dieser Zeile
p1 = arr[rnd1.nextInt(arr.length)];
eine StackOverflowError

(Wenn ich das Pivot-Element so bestimmen lasse "int pivot = arr[(left + right) / 2];" klappt der QuickSort, nur damit ihr wisst, dass der Algorithmus funktioniert.

Hier einmal mein Code

//Aufruf der Methode im Konstruktor
quicksortRandom(arr3, 0, arr1.length-1);

    void quicksortRandom(int arr[], int left, int right)
    {
        int index = partition3(arr, left, right);
        if (left < index - 1)
            quicksortRandom(arr, left, index - 1);
        if (index < right)
            quicksortRandom(arr, index, right);
    }
    int partition3(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
     
        // Vergleichselement Pivot bestimmen
        int p1=0, p2=0, p3=0;
        int pivot = 0;

        Random rnd1 = new Random();
        Random rnd2 = new Random();
        Random rnd3 = new Random();

        if(arr.length>=3)
        {
            p1 = arr[rnd1.nextInt(arr.length)];   //Hier ist das Problem
            p2 = arr[rnd2.nextInt(arr.length)];
            p3 = arr[rnd3.nextInt(arr.length)];

            if (p2<p1 && p3>p1 || p2>p1 && p3<p1)  
            {
                pivot = p1;
            }
            if (p1<p2 && p3>p2 || p1>p2 && p3<p2)  
            {
                pivot = p2;
            }
            if (p1<p3 && p2>p3 || p1>p3 && p2<p3)  
            {
                pivot = p3;
            }

            if (p1==p2 || p2==p3 || p1==p3)
            {
                pivot = p1;
            }
        }
        else
        {
            pivot = arr[left];
        }


        while (i <= j)
        {
            vergleicheMitte++;
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
         
            if (i <= j)
            {
                vertauschungenMitte++;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

 

[JStein52]

Ich würde eher vermuten dass er dir zufaellig an dieser Stelle aussteigt weil du eine "Endlosrekursion" produziert hast.

 

[deggit_biber]

Aber wo baue ich die Endlosrekursion?
Nehmen wir einmal diese Zahlenfolge
1,12,5,26,7,14,3,5,2 ArrayGröße(9)

1. Rekursionsschritt:
original Array, 0(left), 8(right)
index wird bestimmt partition3(arr, left, right)
pivot wird bestimmt: arr.length>=3 also ein zufälliger Int-Wert außer ich habe zwei gleiche gewählt, dann wird halt das erst welches ich mit random gewählt hatte genommen.

sagen wir einmal er hätte die 12, 7 und 2 genommen, dann wäre pivot=7

jetzt beginnt das umsortieren, bis links nur noch kleiner oder gleiche Int-Werte und recht nur noch größere oder gleiche wie zum Pivot-Element stehen.

das neue i wird zurückgegeben, wenn ich mich nicht irre müsste das der index 5 sein.

2. Rekursionsschritt
Die Methode ruft sich neu auf aber mit einem kleineren Array
if (left < index - 1)
quicksortRandom(arr, left, index - 1);
if (index < right)
quicksortRandom(arr, index, right);

0<5-1 -> Rekursion linke hälfte
5<8 -> Rekursion linke hälfte

Das Array, welches er jetzt übergibt, ist doch auch kleiner geworden oder? Also müsste das neue Pivot-Element jetzt immer aus diesem kleineren Array gewählt werden oder?

Wie geschrieben, wähle ich das Pivot-Element
so
pivot = arr

;
oder so
pivot = arr[(left + right) / 2];

klappt der Algorithmus, keine Endlosrekursion.

Es wäre sehr sehr lieb, wenn ihr mir da weiterhelfen könntet.
Viele Grüße,
Deggit​

 

[JStein52]

Die Methode ruft sich neu auf aber mit einem kleineren Array

Wieo mit einem kleineren Array ? Es ist doch immer daselbe, oder übersehe ich was ?

 

[deggit_biber]

ja stimmt, das Array ist immer das selber nur left und right verändern sich.

Da könnte dann auch der Fehler liegen, weil ich das Pivot-Element immer über das ganze Array bilden lasse.

Habt Ihr/du eine Idee, wie ich das Pivot-Element jetzt nur aus den Element der neuen "Teilbereiche" bilden lassen kann?

also wie modifiziere ich mein
p1 = arr[rnd1.nextInt(arr.length)];

arr.length muss also durch eine Formel von left oder right ersetzt werden, die bei jedem Rekursionsschritt zum neuen Teilbereich passt

 

[JStein52]

p1 = arr[left+rnd1.nextInt(right-left)];

??
Aber ohne Gewähr weil ich deinen Algo noch nicht ganz durchschaut habe

 

[deggit_biber]

Ja genau, lift-right bedeutet, er wählt einen Wert innerhalb dieser beider Grenzen, richtig?

Habe die Zeile jetzt so angepasst

p1 = arr[left+rnd1.nextInt(left-right)];

bekomme jetzt einen anderen Fehler aber in der gleichen Zeile
Fehler:
java.lang.illegalArgumentException:
bound must be positiv (in java.util.Random)

bedeutet dies, ich verwende auch negative Grenzen? so deute ich es

Hier einmal ein Link zum Verständnis meines Codes
http://www.algolist.net/Algorithms/Sorting/Quicksort

 

[deggit_biber]

ich überlege gerade, ob ich schummeln sollte. ;-)

Das Problem scheinen ja jetzt die negativen Werte zu sein. Wenn ich vorher also eine If-Abfrage machen, um zu untersuchen, ob left/right negativ sind.
Wenn ja, wähle ich das pivot einfach als index 0. Bei nein lasse ich es wie oben berechnen.

Was meinst du dazu? jetzt müsste ich nur noch wissen, wie man Int-Werte auf Negativität hin überprüft ;-)

Ach ich bin total durch, einfach schauen ob left/rigth<0

Mach ich mal eben mal sehen, ob es was bringt

 

[deggit_biber]

ne klappt leider auch net

habt das jetzt so angepasst

if (arr.length<3)
        {
            pivot = arr[0];
        }
      
        if (arr.length>=3 && left>=0 && right>=0)
        {
            p1 = arr[rnd1.nextInt(left-right)]; 
            p2 = arr[rnd2.nextInt(left-right)];
            p3 = arr[rnd3.nextInt(left-right)];

            if (p2<p1 && p3>p1 || p2>p1 && p3<p1)   
            {
                pivot = p1;
            }
            if (p1<p2 && p3>p2 || p1>p2 && p3<p2)   
            {
                pivot = p2;
            }
            if (p1<p3 && p2>p3 || p1>p3 && p2<p3)   
            {
                pivot = p3;
            }

            if (p1==p2 || p2==p3 || p1==p3) 
            {
                pivot = p1;
            }
        }

Bekomme beim Ausführen immer noch diesen Fehler
java.lang.illegalArgumentException:
bound must be positiv (in java.util.Random)

 

[Meniskusschaden]

Du solltest vielleicht noch mal den Vorschlag von @JStein52 aus Post #9 genau mit deiner Umsetzung in Post #10 vergleichen. Dann wird auch klar, warum du negative Werte bekommst.

 

[Xyz1]

Ich kann später ein Programmablaufplan (PAP) erstellen, falls das etwas nützt^^

 

[JStein52]

Dann wird auch klar, warum du negative Werte bekommst.

Tip: left ist kleiner right

 

[deggit_biber]

ja jetzt ist es klar. ich bin ja so ein depp!!!

Aber kannst du mir noch einmal
p1 = arr[left+rnd1.nextInt(right-left)];
erklären?

ist hier left die erste Grenze und right-left die zweite?
Warum schreibe ich nicht
p1 = arr[left+rnd1.nextInt(right)];
?
Ich glaube ich habe das ganze noch nicht geblickt!

vielen lieben Dank für eure Hilfe

 

[JStein52]

public int nextInt(int bound)

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.

 

[deggit_biber]

ok int nextInt(int bound) macht zwischen 0 und bound das verstehe ich.

Aber wie
p1 = arr[left+rnd1.nextInt(right-left)];
zwischen left(min) und right(max) macht, dass verstehe ich noch nicht. warum das right-left?

 

[JStein52]

Es wird zu left eine zufaellige Zahl zwischen 0 und right-left dazuaddiert. Und right-left ist der "Ausschnitt" des arrays der dich interessiert.

Edit: evtl. fehlt noch ein +1 (right-left+1) je nachdem was du willst.

 

[deggit_biber]

ahhh jetzt hab ichs.

Sagen wir der Ausschnitt geht von index 5 bis 10

dann wird eine Zufallszahl zwischen 5 und 10 so gebildet

left(5) + eine zufällige Zahl die zwischen right-left liegt.

ich muss dabei rigth-left nehmen, damit keine 11,12,usw. entstehen kann

 

[DefconDev]

Also der der Code aus dem ersten post ist nach meinem Verständnis absolut falsch. Was passiert wenn zwei zahlen den selben Wert besitzen. Was geschieht wenn z1 größer als z2 und größer als z3... die Mitte wurde nicht gefunden.