Fragen zu Quellcode QuickSorter

[Den_nis]

Moin moin!
Meine Gruppe hat als Auftrag bekommen, ein Quicksort-Algorithmus zu programmieren und da ich derjenige bin, der momentan nichts zu tun hatte, fiel die Aufgabe mir zu. Dachte, dass sei nicht so kompliziert, aber nun ja.
Ich habe dann mal bei euch im Forum, bei google und bei Wikipedia gesucht und bin schlußendlich auf diesen (siehe unten) Quellcode gestoßen, denn ich irgendwie mit einbauen möchte. Ich habe jetzt aber das Problem, dass ich einige Dinge hierbei nicht verstehe und da bisher keine zufriedenstellende Antwort gefunden habe...

1. Was besagt die Zeile this.a=a; - wozu ist dieser Schritt gut.
1.1 Benötige ich das überhaupt, wenn ich mit Array-Labels arbeite, deren Menge bereits durch ein Variable "Anzahl" geregelt ist?
2. Was besagt hinter den beiden While-Schleifen dieses merkwürdige I++ bzw j--
3. n=a.length <- wozu ist das im Quelltext drinne? Ich habe da den Sinn nicht ganz entnehmen können
T'schuldigung falls das dumme Fragen sind, aber wir sind alle nach nicht allzu lange mit Java beschäftigt und haben bisher hauptsächliche theoretische Kenntnisse erlangt (Programmiert haben wir bisher eher Klein-Kram, wie etwa einen Geld-Umrechner). Würde mich trotzdem über Antworten freuen

public class QuickSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
    }

    private void quicksort (int lo, int hi)
    {
        int i=lo, j=hi;
        int x=a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j)
        {
            while (a[i]<x) i++;
            while (a[j]>x) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class QuickSorter

Quelle:
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm

 

[dieta]

Das n dient dazu, dass schnelle (eben nur mit "n" anstatt mit "a.length" auf die scheinbar häufiger gebruachte Länge von a zugegriffen werden kann.
Das this.a = a dient dazu, die globale Variable a, auf die über this.a zugegriffen wird, auf den Wert von a, das der Methode übergeben wurde, zu setzen. Das geht nur so, da das übergebene a das globale "überdeckt".
das i++ und j-- bedeutet nur, dass i um eins erhoht bzw. j um eins verringert wird. Man könnte auch schreiben "i = i + 1" und "j = j - 1".

 

[Den_nis]

Vielen dank,
aber zu dem n -> das kommt doch im weiteen Verlauf gar nicht vor oder habe ich das jetzt was grundlegendes Übersehen (passiert mir öfter, wenn ich schon mehrere Stunde an sowas arbeite)?

Ist dieser Quelltext eigentlich Problemlos in eine Programm mit Arrays, Buttons und vor in eine While-Schleife einzubauen, aber muss ich was bestimmtes beachten?

 

[dieta]

Du hast recht, das n kannst du ruhig löschen, wenn du aus dem quicksort(0, n-1); ein quicksort(0, a.length-1); machst.
Die Methoden sollten nicht eigentlich probelmlos in jede bestehende Anwendung integrieren lassen.

 

[Den_nis]

Vielen Dank,
allerdings habe ich schon das nächste Problem:

Ich möchte versuchen diese Methoden in das Programm zu integrieren, sie sollen aber erst über einen Button gestartet werden. Also habe ich dem Programm gesagt, er solle die im TextField-Array eingegeben Zahlen auf die Label-Arrays übertragen, sobald der Button gedrückt wird. Funktioniert auch. . . dann aber wollte ich einen Methoden-Verweis auf diese Methoden in den Button einbauen. Also mit:

Methodenname();

unten kommt dann

public void Methodenname(int[]a)

Das allerdings funktioniert nicht (liegt an dem "int[]a"). Bin da jetzt emsig am rummwuseln im Quelltext, aber wie ich das hinbekommen entzieht sich noch meiner Kenntniss. Würde da gerne noch einmal Hilfe in Anspruch nehmen.
Ist es unmöglich direkt aus einem Button auf eine solche Methode zu leiten oder gibt es da einen Trick?

 

[dieta]

Du musst der Methode das Array, das sortiert werden soll, übergeben:

methodenname(dasArray);

 

[Den_nis]

Also müsste ich auch beim ersten schon (int[]a) einsetzen? - Das nämlich hatte ich gemacht und es hatte nicht funktioniert, wenn ich mich recht erinnere . . . oder habe ich das jetzt missverstanden?

 

[dieta]

Naj... Die methode sort(int[]) erwartet als Argument das Array, das sie sortieren soll.
Das musst du ihr schließlich irgendwie übergeben.
Poste vllt. etwas Code.

 

[Den_nis]

So sieht mein Programm momentan aus (habe eben nochmal schnell die Methodenübergabe eingefügt)

import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class QuicksorterA extends Applet implements ActionListener
{                                                                               //public class Quicksorter beginnt
int max=5;                                                                      //"max" wird als Integer definiert und bekommt den wert 5 zugewiesen
int []a=new int[max];                                                          //Es wird ein Array erzeugt
int c;
String s1, s2;
TextField TF[]=new TextField[max];
Label LA[]=new Label[max];
Button b1=new Button(" Eingabe ");

       public QuicksorterA()                                                    //public QuicksorterA beginnt
       {                                                                        //public Quicksorter beginnt
       setLayout(new GridLayout(max+1,2,1,1));                                  //Layout wird festgelegt (max+1 Zeilen, zwei Spalten)
       for (int i=0; i<max; i=i+1)                                              //For-Schleifenkopf (i ist Integer mit wert 0, wird durchgeführt solange i kleiner als max, jeder Schritt erhöht i um 1
       {                                                                        //For-Schleife beginnt
       TF[i]=new TextField("",8);
       LA[i]=new Label("");
       add(TF[i]);
       add(LA[i]);
       add(b1);
       b1.addActionListener(this);
       }                                                                        //For-Schleife endet
       }                                                                        //public Quicksorter endet
       
       public void actionPerformed(ActionEvent e)
       {                                                                        //public void actionPerf... beginnt
       if(e.getSource()==b1)
       {                                                                        //IF-b1-Definition beginnt
       for (int i=0; i<max; i++)                                                //For-Schleifenkopf (siehe For-Schleife oben)
       {                                                                        //For 1.1 beginnt
       s1=TF[i].getText();
       a[i]=Integer.parseInt(s1);
       LA[i].setText(""+a[i]);
       sort();                                                                  //Methodenübergabe
       }                                                                        //For 1.1 endet
       }                                                                        //IF-b1-Defintion endet
       }                                                                        //public void actionPerf... endet
       public void sort(int [] a]
       {
       //hier soll die die "mir fremde Methode entstehen"
       }


}                                                                               //public class QuicksorterA endet

 

[dieta]

Ah... dann musst du das so aufrufen:

sort(a);

 

[Den_nis]

Fantastisch, danke. . .
Das nächste Problem kommt bestimmt, aber erstmal bin ich einen riesigen Schritt weiter glaube ich.

Als nächstes kommt dann der Quicksort-Algorithmus langsam aber sicher da rein. Wenn ich das richtig sehe, muss ich bei dem "fremden Quellcode" noch für die Bildschirm-Ausgabe sorgen und dann die Aufteilung in zwei Felder irgendwie schaffen, damit dort auch wieder ein Quicksort-Algorithmus laufen kann^^ - Aber jetzt bin ich einen riesen Schritt weiter, glaube ich . . . sollten weitere Probleme auftauchen, melde ich mich hier wieder.

 

[Den_nis]

Ich glaube ich habe langsam echt zu viel in diesem Programm rummgewuselt, denn mittlerweile sehe ich "den Wald vor lauter Bäumen" nicht mehr. . . das Programm (nur die basis, nicht das ganze fertige) läuft, aber es verändert die zahlen . . . . aus 5 - 4 - 3 - 2 - 1 wird immer 1 2 2 3 3 <- ich habe den Quelltext jetzt mehrfach durch, finde aber den Fehler nicht mehr . . . vielleicht irgendwas völlig simples, wonach man sich durch das ewige Programmieren todsuchen kann . . . Ich würde hier gerne nochmals den neuen Quelltext reinsetzen und wäre sehr dankbar, wenn sich jemand vielleicht die Zeit nehmen mag und den Fehler suchen möchte . . . Randnotiz: Keine Informatik-Anfänger auf Zeitddruck an einem QUicksortprogramm arbeiten lassen, wenn diese nicht richtig dafür vorbereitet wurden . . .

Hier nochmal der Code . . . vielleicht einfach im eigenen java-editor einfügen, damit ihr besser sehen könnt, welches Problem sich hier ergibt - wäre für weitere Hilfe echt dankbar

import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class QuicksorterA extends Applet implements ActionListener
{                                                                               //public class QuicksorterA beginnt
int max=5;                                                                      //"max" wird als Integer definiert und bekommt den wert 5 zugewiesen
int []a=new int[max];                                                           //Es wird ein Array erzeugt
int c;
private int n;
String s1, s2;
TextField TF[]=new TextField[max];
Label LA[]=new Label[max];
Button b1=new Button(" Eingabe ");

       public QuicksorterA()                                                    //public Quicksorter beginnt
       {                                                                        //public Quicksorter beginnt
       setLayout(new GridLayout(max+1,2,1,1));                                  //Layout wird festgelegt (max+1 Zeilen, zwei Spalten)
       for (int i=0; i<max; i=i+1)                                              //For-Schleifenkopf (i ist Integer mit wert 0, wird durchgeführt solange i kleiner als max, jeder Schritt erhöht i um 1
       {                                                                        //For-Schleife beginnt
       TF[i]=new TextField("",8);
       LA[i]=new Label("");
       add(TF[i]);
       add(LA[i]);
       add(b1);
       b1.addActionListener(this);
       }                                                                        //For-Schleife endet
       }                                                                        //public Quicksorter endet
       
       public void actionPerformed(ActionEvent e)
       {                                                                        //public void actionPerf... beginnt
       if(e.getSource()==b1)
       {                                                                        //IF-b1-Definition beginnt
       for (int i=0; i<max; i++)                                                //For-Schleifenkopf (siehe For-Schleife oben)
       {                                                                        //For 1.1 beginnt
       s1=TF[i].getText();
       a[i]=Integer.parseInt(s1);
       LA[i].setText(""+a[i]);
       sort(a);                                                                 //Methodenübergabe
       }                                                                        //For 1.1 endet
       }                                                                        //IF-b1-Defintion endet
       }                                                                        //public void actionPerf... endet
       public void sort(int [] a)
       {                                                                        //public void sort beginnt
       this.a=a;
       n=a.length;
       quicksort(0, n-1);
       }                                                                        //public void sort endet
       private void quicksort (int y1, int y2)
       {                                                                        //private void quicksort beginnt
       int z1=y1, z2=y2;
       int pivot=a[(y1+y2)/2];
       
           while(z1<=z2)                                                        //Schleifenkopf-While-1
           {                                                                    //While 1 beginnt
           while(a[z1]<pivot) z1++;
           while(a[z2]>pivot) z2--;
           if(z1<=z2)                                                           //IF-Schleifenkopf IF 1
           {                                                                    //IF-1 beginnt
           tausche(z1, z2);
           z1++;
           z2--;
           }                                                                    //IF-1 endet
           }                                                                    //While 1 endet
           
           if (y1<z2) quicksort(y1, z2);
           if (z1<y2) quicksort(z1, y2);
       }                                                                        //private void quicksort endet
       private void tausche(int z1, int z2)
       {                                                                        //private void tausche beginnt
       int k=a[z1];
       a[z1]=a[z2];
       a[z2]=k;
       LA[z1].setText(""+a[z1]);
       LA[z2].setText(""+a[z2]);
       }                                                                        //private void tausche endet

}                                                                               //public class Quicksorter endetA

 

[Ich nochmal^^]

Bin auf der Fehlersuche einen schritt weitergegekommen:
Es scheint, als würde das Programm zwar alle Zahlen behalten, aber einige rauswerfen und dafür andere doppelt nehmen. Falls das jemandem hilft, mir zu helfen. Ich teste momentan eher dumm rumm, als dass ich das irgendetwas sinnvolles tun würde

 

[Den_nis]

Das Problem hat sich möglicherweise durch stupides rummprobieren erledigt. Ich hoffe es