Hi Leute,
irgendwie ist mein Quicksort- Algorithmus voll langsam:/ kann mir da wer helfen?
irgendwie ist mein Quicksort- Algorithmus voll langsam:/ kann mir da wer helfen?
Java:
public class Sortieren
{
// Deklaration Array
private int []Array;
/**
* Konstruktor für Objekte der Klasse Sortieren
*/
public Sortieren()
{
// Array initalisieren mit Zufallslänge
Array = new int[(int)(Math.random()*10)];
// Array Zufallszahlen zuweisen
for(int i= 0; i < Array.length; i++)
{
Array[i] = (int)(Math.random()*10);
}
}
/**
* Konstruktor für Objekte der Klasse Sortieren
*
* @param Laenge Länge des Arrays
*/
public Sortieren(int Laenge)
{
// Array initalisieren mit groeße
Array = new int[Laenge];
// Array Zufallszahlen zuweisen
for(int i= 0; i < Array.length; i++)
{
Array[i] = (int)(Math.random()*10);
}
}
/**
* Main Methode der Klasse Sortieren (Selbstinitialisierung)
*
* @param args Wird vom System benötigt, um Objekt zu konstruieren
*/
public static void main(String[] args)
{
// Selbstinitialisierung und Programm starten
(new Sortieren()).start();
}
/*
/**
* Main Methode der Klasse Sortieren (Mit Hilfsobjekt)
*
* @param args Wird vom System benötigt, um Objekt zu konstruieren
*/
/*
public static void main(String[] args)
{
Sortieren s = new Sortieren();
s.start();
}
*/
/**
* Methode, die den eigentlichen Programmablauf durchgeht
*/
public void start()
{
System.out.println("quickSort:");
System.out.println();
long startZeit = System.nanoTime(); // Anfangszeit für Laufzeitberechnung
this.sortieren(Array, 0, Array.length-1);
System.out.println("Benötigte Zeit zum Sortieren in Nanosekunden: "+(System.nanoTime()-startZeit)+""); //Laufzeitberechnung
System.out.println();
this.arrayAusgeben();
this.neueWerte();
System.out.println("bubbleSort:");
System.out.println();
startZeit = System.nanoTime();
this.bubbleSort();
System.out.println("Benötigte Zeit zum Sortieren in Nanosekunden: "+(System.nanoTime()-startZeit)+""); //Laufzeitberechnung
System.out.println();
this.arrayAusgeben();
this.neueWerte();
System.out.println("bubbleSort(Rekuriv):");
System.out.println();
startZeit = System.nanoTime();
this.bubbleSortRekursiv();
System.out.println("Benötigte Zeit zum Sortieren in Nanosekunden: "+(System.nanoTime()-startZeit)+""); //Laufzeitberechnung
System.out.println();
this.arrayAusgeben();
this.neueWerte();
System.out.println("selectionSort:");
System.out.println();
startZeit = System.nanoTime();
this.selectionSort();
System.out.println("Benötigte Zeit zum Sortieren in Nanosekunden: "+(System.nanoTime()-startZeit)+""); //Laufzeitberechnung
this.arrayAusgeben();
}
/**
* Methode, um das sortierte Array auszugeben
*/
private void arrayAusgeben()
{
//Array mittels for-Schleife ausgeben
for(int i = 0; i < Array.length; i++)
{
System.out.println("Stelle: "+i+"; Inhalt: "+Array[i]+"");
}
System.out.println();
}
/**
* Methode, um den Feldern des Arrays neue Zufallswerte zuzuweisen
*/
public void neueWerte()
{
// Array Zufallszahlen zuweisen
for(int i= 0; i < Array.length; i++)
{
Array[i] = (int)(Math.random()*10);
}
}
/**
* Methode, um das Array nach dem bubbleSort Algorithmus zu sortieren
*/
public void bubbleSort()
{
// Jedes Feld mit jedem vergleichen
for(int i = 0; i < Array.length; i++)
{
for(int j = 0; j < Array.length-1; j++)
{
// Wenn Array an der Stelle i größer ist, als Array an der Stelle j beide Werte tauschen aufrufen
if(Array[i] < Array[j])
{
int help = Array[i];
Array[i] = Array[j];
Array[j] = help;
}
}
}
}
/**
* Methode, um das Array nach dem bubbleSort Algorithmus(rekursiv) zu sortieren
*/
public void bubbleSortRekursiv()
{
// Inhalt des Feldes mit anderen Feldern des Arrays vergleichen
for(int i = 0; i < Array.length-1; i++)
{
// Wenn Array an der Stelle i größer ist, als Array an der Stelle j beide Werte tauschen und bubbleSort rekursiv aufrufen
if(Array[i] > Array[i+1])
{
int help = Array[i];
Array[i] = Array[i+1];
Array[i+1] = help;
bubbleSort();
}
}
}
/**
* Methode, um das Array nach dem selectionSort Algorithmus zu sortieren
*/
public void selectionSort()
{
// an der ersen Stelle bis zum Ende des Arrays hochzählen
for(int i = 0; i < Array.length-1; i++)
{
// ab Stelle i mit den weiterfolgenden Werten vergleichen
for(int j = i + 1; j < Array.length; j++)
{
// wenn der Wert an j kleiner ist als an i, Werte tauschen
if(Array[j] < Array[i])
{
int help = Array[i];
Array[i] = Array[j];
Array[j] = help;
}
}
}
}
/**
* Methode um den Quicksort Algorithmus in Gang zu setzen
*/
public void quickSort()
{
// Aufruf der rekursiven Methode sortieren
sortieren(Array, 0, Array.length-1);
}
/**
* Rekursive Methode zum Sortieren von Arrays
*
* @param Array[] zu sortierendes Array
* @param links linke Stelle des zu sortierenden Raumes des Arrays
* @param rechts rechte Stelle des zu sortierenden Raumes des Arrays
*
* @return Array, in dessen linker Hälfte alle Objekte kleiner sind als das "Mittelobjekt" und auf der rechten Seite größer
*/
private static int[] sortieren(int Array[], int links, int rechts)
{
// Bedingung prüfen, ob die Stelle links vor rechts ist, ansonsten wird Array wie gehabt zurückgegeben (Abbruchbedingung für die Rekursive Funktion + Überprüfung Zahlendreher/... des Anwenders
if(links < rechts)
{
//Erster Teildurchgang und die Position von dem "Mittelobjekt" wird gespeichert
int teiler = teile(Array, links, rechts);
// Funktion wird nochmal durchgegangen
sortieren(Array, links, teiler);
// Durchgang für die rechte Seite des Arrays
sortieren(Array, teiler+1, rechts);
}
// Arrayhälfte, bei links alles kleiner ist als das "Mittelobjekt" und rechts alles größer ist, beim finalen Durchgang sortiertes Array
return Array;
}
/**
* Rekursive Methode zum Sortieren von Arrays
*
* @param Array[] zu sortierendes Array
* @param links linke Stelle des zu sortierenden Raumes des Arrays
* @param rechts rechte Stelle des zu sortierenden Raumes des Arrays
*
* @return Position des "Mittelobjektes" oder "Schwenkobjektes" des Arrays
*/
private static int teile(int Array[], int links, int rechts)
{
// Hilfsvariablen erstellen
int pivot = Array[rechts]; // "Mittelobjekt", welches zur Teilung des Arrays benutzt wird( Links neben ihm kleinere Zahlen, rechts größere)
int i = links;
int j = rechts-1;
while(i < j) {
/* // prüfen, an welcher Stelle Zahl ist, für die Bedingung ( Zahl muss kleiner sein als "Mittelobjekt" und innerhalb des Arrays sein( Damit nicht Arrayoutofbounds auftritt)) nicht zutrifft
for( i = i; Array[i] < pivot && i < rechts-1; i++)
{
}
// prüfen, an welcher Stelle Zahl ist, für die Bediungung ( Zahl muss größer sein als "Mittelobjekt" und innerhalb des Arrays sein( Damit nicht Arrayoutofbounds auftritt)) nicht zutrifft
for( j = j; Array[j] >= pivot && j > links; j--)
{
}*/ // Diese Abfrage funktioniert, ist aber langsam
// prüfen ob i und j auf der richtigen Seite sind (links: kleiner als pivot, rechts: größer als pivot)
if(i < j){
// Werte an Stellen i und j tauschen
int tauschen = Array[i];
Array[i] = Array[j];
Array[j] = tauschen;
j--; // Übernimmt das runterzählen von der for Schleife
}
else
{
i++; // Übernimmt das hochzählen von der for Schleife
}
}
// Da der Pivotwert immer noch ganz rechts ist, prüfen, auf welcher Seite dieser stehen muss (links/rechts)
if(Array[i] > pivot){
// Werte an Stellen i und rechts tauschen
int tauschen = Array[i];
Array[i] = Array[rechts];
Array[rechts] = tauschen;
}
// gibt Position von Pivot zurück, damit dieses nochmal als Teiler verwendet werden kann (Oder halt die Zahl danach)
return i;
}
}
