BlueJ QuickSort in BlueJ umsetzen

I_Parzival_I

Mitglied
Hi Leute,
Letztens wurde mir die Aufgabe erteilt den Sortier-Algorithmus Quicksort in BlueJ umzusetzen.
Gestern habe ich angefangen und versucht loszulegen bin aber kläglich gescheitert.:oops:o_O;)
Wir sollen ein Array mit einstellbar vielen Zellen erstellen und per Eingabefenster soll man die zu sortierenden Zahlen dann eingeben können.
Wobei der Algorithmus dann das sortierte Array ausgeben soll.
Ich hoffe jemand kann mir helfen oder wenigstens einen Denkanstoß geben!
MfG Parzival:p
 
K

kneitzel

Gast
Woran scheitert es denn?
- Zahlen kannst Du vom User eingeben lassen?
- Wie man ein Array erzeugt, weisst Du?
- Schleifen kennst Du?
- Dann natürlich der QuickSort Algorithmus
 

I_Parzival_I

Mitglied
Also woran es scheitert ist die Implementierung von Quicksort in BlueJ und dann das Problem mit der Eingabe.
Dies ist mein aktuelles Programm:
 

Anhänge

  • Quick.txt
    846 Bytes · Aufrufe: 16
K

kneitzel

Gast
Also um Eingaben zu lesen solltest Du Dir die Klasse Scanner einmal ansehen.

Und kannst Du den QuickSort Algorithmus in eigenen Worten wiedergeben? Am Besten in einer Art Pseudocode?

Dann können wir dies langsam erarbeiten.
 

I_Parzival_I

Mitglied
1. Danke für den Tipp mit dem Scanner das werde ich auf jeden Fall machen.
2. Ich weiß wie Quicksort funktioniert, weiß nur leider nicht wie man die Übertragung des Pivot Elements in Java Umsetzen kann.

So sieht mein momentaner Arbeits-Status aus. Den String versuche ich jetzt noch durch den Scanner ersetzen :p;)

Bin leider noch Anfänger deshalb möchte ich durch diese Projektarbeit auch was lernen also habt bitte erbarmen mit mir:):oops:
 

Anhänge

  • Quick.txt
    983 Bytes · Aufrufe: 16

mihe7

Top Contributor
Ich weiß wie Quicksort funktioniert, weiß nur leider nicht wie man die Übertragung des Pivot Elements in Java Umsetzen kann.
Hier geht keiner davon aus, dass Du nicht weißt, wie Quicksort funktioniert. Es hilft jedoch, wenn man sich dazu zwingt, das Problem zu beschreiben, um daraus Code zu entwickeln.

Wenn es nur um das Tauschen zweier Elemente im Array geht, so brauchst Du ein Variable, die temporär ein Element aufnimmt, um z. B. die Element an Index a und b zu tauschen:

Java:
int tmp = feld[a];
feld[a] = feld[b];
feld[b] = tmp;

Übrigens, Du kannst Deinen Java-Code direkt hier einfügen, dann aber bitte in Code-Tags, also: [code=Java]Dein Code[/code]
 

I_Parzival_I

Mitglied
Also dies ist bisher der Teil des Programms zum einlesen der Werte.
Aber da der Scanner ja die Konsole als String einliest, ich die Werte aber als Integer brauche komm ich nicht weiter.
Kann mir jemand helfen und sagen wie ich die Werte als Integer einlesen kann?
Java:
package QuickSort;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class qicksort2
{
    private int Länge;
    public static void main(String[] args) {
        int i=0;
        int[] Liste = new int[Länge];
        Scanner scanner = new Scanner(System.in);
        while (true){
            String s = scanner.next();
            if(s.equals("q")) break;  //Ich muss den String zum Integer machen damit er im weiteren Programm Sortiert werden kann
            System.out.println(s);
            int Liste[i] = s;
            i++;
        }
        System.out.println("Bye...");
        scanner.close();
    }
 
K

kneitzel

Gast
Also Du kannst einen String parsen um den darin enthaltenen Integer zu bekommen: Integer.parseInt(string) wäre da ein Aufruf.
https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html

Oder Du liest direkt eine Zahl ein (Dann kann aber kein "q" angegeben werden): scanner.nextInt() wäre da der Aufruf.
https://docs.oracle.com/javase/7/docs/api/java/util/Scanner.html

Und sollte die Länge nicht auch erst eingegeben werden? (Und bitte keine Variablen mit Umlauten! Also bitte Laenge oder so nutzen!) Also wäre der Pseudocode doch:
- Eingabe der gewünschten Länge
- Erzeugen des Arrays
- Schleife um Länge-Mal einen Wert einzulesen und in dem array zu speichern
 

I_Parzival_I

Mitglied
So ich habe jetzt erstmal die Eingabe fertig gestellt.
Ich habe jetzt nur noch beim einsetzen ein Problem an der markierten Stelle.
[Ich gebe zB. 5 (als Länge ein) und dann 1 2 3 4 5]
Kann mir jemand weiterhelfen wäre echt super ! ;)

Java:
package QuickSort;

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class qicksort2
{
    private int Laenge = 0;
    int[] Liste = new int[Laenge];
    public  void main(int Laenge) 
    { 
        int s=1;
        int Zaeler=0;
        int tausche;
        int links = 0;
        int rechts = Laenge-1;
        int nachlinks = rechts;
        int nachrechts = links;
        Scanner sc = new Scanner(System.in); 
        while (s != 0){ 
            s = sc.nextInt();   
            System.out.println(s);
            Liste[Zaeler] = s;      // <-- Beim Durchlaufen des Algorhythmusses bekomme ich hier eine Fehlermeldung
            Zaeler++;
        } 
        System.out.println("Bye..."); 
        sc.close(); 
        
        
        
        if (nachrechts < nachlinks)
        {
            int pivot = Liste [(nachrechts + nachlinks)/2];
            while (nachrechts <= nachlinks)
            {
                while ((nachlinks > rechts) && (Liste[nachrechts] > pivot))
                    nachlinks--;
                if (nachrechts <= nachlinks)
                    {
                    tausche = nachrechts;
                    nachrechts = nachlinks;
                    nachlinks = tausche;
                    nachrechts++;
                    nachlinks--;
                    }
            } 
        }
        System.out.println(Liste);
        
        
    } 

    
    
}
 
K

kneitzel

Gast
Das, was Du schreibst, stimmt nicht mit dem überein, was Du als Code gepostet hast.

Du willst erst die Größe angeben, aber die Größe ist generell 0 (weil Laenge so initialisiert wird und nie verändert).

Daher wirst Du wahrscheinlich eine Index out of Bounds Exception bekommen, weil Du versuchst auf ein Element zuzugreifen, dass es nicht gibt.

Also einbauen, dass Du die Größe eingeben kannst und dann ein Array mit der entsprechenden Größe erstellen. Und dann nicht die Eingabe als Abbruchkriterium nehmen sondern so lange abfragen, bis das Array gefüllt ist. Oder meinst Du nicht?
 

I_Parzival_I

Mitglied
Ich verstehe nur nicht warum er mir nicht das eingegebene Array ausgibt sondern
bei den Eingaben
Länge = 4
und dann
2 5 3 6
gibt er mir das aus:
[I@617d6168

Java:
package QuickSort;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Qicksort
{
    public  void main(int Laenge)
    {
        int [] Liste = new int[Laenge];
        int s=1;
        int Zaeler=0;
        Scanner sc = new Scanner(System.in);
        while (Zaeler < Laenge)
        {
            s = sc.nextInt();
            Liste[Zaeler] = s;
            Zaeler++;
        }
        System.out.println("Alle zahlen beisammen!");
        sc.close();
       
        System.out.println(Liste);
    }
}
 
K

kneitzel

Gast
Das ist der default für Object. Wenn Du eine vernünftige Ausgabe haben möchtest, musst Du die selbst schreiben. Hintergrund dabei ist, dass java ja nicht wissen kann, wie Du Dein Array ausgegeben haben möchtest. Es gibt aber auch fertige Implementationen, so z.B. Arrays.toString(array), welche den Inhalt des Arrays in [ ... ] ausgibt, wobei die Inhalte durch ein Komma getrennt sind.
 

I_Parzival_I

Mitglied
Danke jetzt ist aber trotztem noch ein leiner Fehler mit der Konsole da sie nicht das schreibt was sie soll!:eek::mad:o_O
Java:
package QuickSort;

import java.io.*;
import java.util.*;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Qicksort
{
    public  void Sortieren(int Laenge)
    {
        int [] Liste = new int[Laenge];
        int s=1;
        int Zaeler=0;
        System.out.println("Bitte geben sie nun ihre Zahlen ein:");
        Scanner sc = new Scanner(System.in);
        while (Zaeler < Laenge)
        {
            s = sc.nextInt();
            Liste[Zaeler] = s;
            Zaeler++;
        }
        sc.close();
        System.out.println("Alle zahlen beisammen");
        System.out.println(Arrays.toString(Liste));
        System.out.println("Bitte warten sie Zahlen weden sortiert!");
        sortierung(Liste,0,Laenge-1);
    }
 
 
    private int partition(int Liste[], int klein, int groß)
    {
        int Trenner = Liste[groß];
        int i = (klein-1); // index of smaller element
        for (int j=klein; j<groß; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (Liste[j] <= Trenner)
            {
                i++;

                // swap arr[i] and arr[j]
                int Tauscher = Liste[i];
                Liste[i] = Liste[j];
                Liste[j] = Tauscher;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int Tauscher = Liste[i+1];
        Liste[i+1] = Liste[groß];
        Liste[groß] = Tauscher;

        return i+1;
    }


 
    private void sortierung(int Liste[], int klein, int groß)
    {
        if (klein < groß)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(Liste, klein, groß);

            // Rekursiever Aufrufder zu sortierenden Seiten
            sortierung(Liste, klein, pi-1); //Linker Kasten
            sortierung(Liste, pi+1, groß); //Rechter Kasten
        }
        else
        {
            System.out.println(Arrays.toString(Liste));
        }
    }
}
Dies gibt die Konsole aus:
Code:
Bitte geben sie nun ihre Zahlen ein:
4
2
3
7
18
[4, 2, 3, 7, 18]
Bitte[4, 2, 3, 7, 18]
Bitte warten sie Zahlen weden sortiert!
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
 

mihe7

Top Contributor
Scheint aber dann ein BlueJ-Problem zu sein. Hier kommt das so raus:
Code:
4
2
3
7
18
Alle zahlen beisammen
[4, 2, 3, 7, 18]
Bitte warten sie Zahlen weden sortiert!
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
[2, 3, 4, 7, 18]
 

Neue Themen


Oben