Quick Sort

A

Ameisenbär

Mitglied
Hallo :)
Und zwar habe ich ein Problem, unsere Aufgabe besteht darin, dass wir uns ein Quelltext von Quicksort suchen sollten und den Quelltext dann kommentieren müssen.
Ich hab nur leider keine Ahnung was in dem Programm vor sich geht..wäre lieb wenn mir jemand ein bisschen helfen würde..vorallem im unteren Teil :)

Java: 
package quick; // Name des Packets,welches verwendet wird

public class QuickSort { // Name der Klasse: QuickSort
	public static void main(String a[]){ // Main-Methode
		  int i; // integer i dekliniert
		  int array[] = {17,24,3,12,7,10 }; // Werte, welche geordnet werden
		  System.out.println(" Quick Sort\n\n"); //Ausgabe auf Bildschirm
		  System.out.println("Werte vor dem Sortieren:\n"); // Ausgabe
		  for(i = 0; i < array.length; i++)//
		  System.out.print( array[i]+"  "); / /Ausgabe
		  System.out.println();
		  quick_srt(array,0,array.length-1);
		  System.out.println();
		  System.out.print("Werte nach dem Sortieren:\n");
		  for(i = 0; i <array.length; i++)
		  System.out.print(array[i]+"  ");
		  System.out.println();}
		  public static void quick_srt(int array[],int low, int n){
		  int lo = low; / integer dekliniert
		  int hi = n; // integer dekliniert
		  if (lo >= n) { // wenn integer lo größer gleich n -
		  return; // wiederholt sich der Vorgang
		  }
		  int mid = array[(lo + hi) / 2]; //
		  while (lo < hi) {
		  while (lo<hi && array[lo] < mid) {
		  lo++;
		  }
		  while (lo<hi && array[hi] > mid) {
		  hi--; }
		  if (lo < hi) {
		  int T = array[lo];
		  array[lo] = array[hi];
		  array[hi] = T;}
		  }
		  if (hi < lo) {
		  int T = hi;
		  hi = lo;
		  lo = T;}
		  quick_srt(array, low, lo);
		  quick_srt(array, lo == low ? lo+1 : lo, n);
		  }
		}





Liebe Grüße Steffi
 
Zuletzt bearbeitet von einem Moderator:
C

chalkbag

Bekanntes Mitglied
Hallo,

ich denke du sollst nicht jede triviale Zeile kommentieren.
Wie Variablen deklariert, Methoden aufgerufen und und wird sollte klar sein.
Auch Kommentare wie "(i >= b) \\ wenn i größer gleich B ist" machen keinen Sinn.
Ein Kommentar soll die Logik erklären, und nicht die Syntax.

Dein Lehrer will eher was in der Richtung wie

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

     wiederhole

         // Suche von links ein Element, welches größer als das Pivotelement ist
         wiederhole solange daten[i] ≤ pivot und i < rechts
             i := i + 1
         ende

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

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

     solange i < j // solange i an j nicht vorbeigelaufen ist 

     // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
   
     falls daten[i] > pivot dann
             tausche daten[i] mit daten[rechts]
     ende
     
     // gib die Position des Pivotelements zurück
    
     antworte i
 ende
Quelle: Quicksort ? Wikipedia
 
S

Steff87

Aktives Mitglied
Hi!
Erst mal ein kleiner Tipp:
Bring den Quellcode in eine schöne, brauchbare Form.
z.B.:
Java: 
public static void main(String a[]){ // Main-Methode
          int i; // integer i dekliniert
          int array[] = {17,24,3,12,7,10 }; // Werte, welche geordnet werden
          System.out.println(" Quick Sort\n\n"); //Ausgabe auf Bildschirm
          System.out.println("Werte vor dem Sortieren:\n"); // Ausgabe

          for(i = 0; i < array.length; i++)//
              System.out.print( array[i]+"  "); / /Ausgabe

          System.out.println();

          quick_srt(array,0,array.length-1);

          System.out.println();
          System.out.print("Werte nach dem Sortieren:\n");

          for(i = 0; i <array.length; i++)
              System.out.print(array[i]+"  ");

          System.out.println();
}
Dann sieht das ganze schon etwas lesbarer aus.

Und noch was:
Der Kommentar in Zeile 22 stimmt nicht. Der Vorgang wird nicht wiederholt, sondern abgebrochen, da der Unteregrenzwert größer oder gleich der Länge des Arrays ist, das übergeben worden ist.

Was hast du bisher schon gemacht?
 
C

chalkbag

Bekanntes Mitglied
Solange du die Funktionsweise eines Quicksort nicht verstehst, wirst du diesen Code nicht verstehen.

Also einfach mal (ich sag's ja gern immer wieder) mit Stift+Papier einen Quicksort durchspielen. Hast du das verstanden, kannst du ja mal mit dem Debugger durchspringen. Dann sollte der Code (dank deiner Notizen auf dem Papier) ja leichter verständlich sein.
Es wäre natürlich leichter, wenn du eine Implementierung mit sprechenden Variablennamen verwendest.

Es gibt auch viele Seiten, die graphisch den Sortieralgorithmus durchgehen, vielleicht hilft das.

Recursive Sorting

[Edit]
Folgende Seite mach auch einen guten Eindruck, auf den ersten Blick.
Sorting Algorithms - QuickSort Tutorial, Example, and Java code
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen


Oben