Quicksort programmieren Probleme

[Jah]

Hallo,
In unserem Informatikkurs (Klassenstufe 12) hat unser Lehrer heute urplötzlich angekündigt, dass alle, die er im Einser-Bereich (also der Note eins (13-15 Punkte)) sieht, ihm bis nächsten Mittwoch ein Quicksort programm programmieren sollen. Wir dürfen hierzu alle gängien Hilfsmittel nutzen, die zu finden sind.
Nun habe ich basierend auf meinem Bubblesort-Programm damit angefangen und das Programm "kann" nun folgendes:
Es hat so viele Textfelder und Labels wie die Variable max vorgibt und es hat zwei Buttons. Ein Button überträgt die Zahlen der Textfelder auf die Labels - das funktioniert.
Nun komme ich zum zweiten Button und möchte hier natürlich den Sortieralogrithmus einbasteln und das "große Problem" fängt da auch schon an. Wir sollen das mittlere Element (das erste oder letzte zu wählen wurde uns strikt verboten) als Pivotelement nehmen. Aber wie mache ich das?
Ich habe daran gedacht die Variable max einfach durch zwei zu teilen, komme dann aber bei einer ungeraden Zahl an Elementen auf eine Kommazahl (bei 5 Elementen (also max = 5) wäre das ja 5 / 2 = 2,5). Ein Feld mit der Zahl 2,5 gibt es aber natürlich nicht.
Mein erstes Problem bei diesem Programm (weitere werden sicherlich folgen) . . . ich erbitte da eure Hilfe

Vielleicht nochmal zum besseren Verständnis die Aufgaben:
- Programmieren sie ein Quicksortprogramm
- Zunächst sollen fünf Zahlen sortiert werden
- Das Programm ist varibel zu gestalten, sodass ohne große Änderungen auch 10, 20, 100 ... Zahlen sortiert werden können
- Kommentiere sie jede(!) Zeile und bereiten sie sich darauf vor, gezielte Fragen beantworten zu können

So nun stehe ich hier im "Regen" und kriege nicht einmal das Pivot-Element definiert.

Also zurück zu meiner Frage:
Wenn ich die Varible max = 5 gesetzt habe und die fünf (vom Nutzer) eingegebenen Zahlen auf die Labels übertragen habe, wie kann ich dann beim zweiten Button das Pivot-Element definieren?

Wäre über schnelle Hilfe dankbar

 

[tfa]

Für int-Werte gilt:

5/2=2

Ganzzahldivision liefert Integer als Ergebnis zurück.

 

[Jah]

Super . . .vielen Dank. Das z.B. wusste ich bisher nicht 🙂
Ich werde es dann einfach mal mit max/2 +1 versuchen, da ich damit ja an sich in jede legitime Mitte bestimme . . . bei einer ungerade Zahl müsste es dann die genaue Mitte ergeben und bei geraden Zahlen "eine der beiden "Mitten". Damit bin ich sicherlich ein Stück weiter, aber vielleicht ergeben sich mir noch mehr Fragen -.-
Erstmal jedenfalls vielen dank

 

[Jah nochmal]

Hm...so richtig weit hat mich meine Idee mit dem max/2+1 nicht gebracht. Das versagt spätestens beim zweiten durchlauf, da ich ja nicht vorher weiß, wo groß die jeweiligen Felder werden.
Ich habe da ein bisschen gegoogelt, aber bisher keine Lösung gefunden, die ich verstehen würde -.-
Mag jetzt vielleicht wirklich doof klingen oder viel verlangt sein, meine Frage, aber wie bestimmt man denn das Pivotelement eines QUicksort-Programms normalerweise . . . in einem fertigen Quelltext sehe ich das irgendwie immer nicht bzw. kann die wichtigen Elemente nicht rauslesen. 😳

Das zweite Problem, dass sich mir stellt ist, dass ich keine Ahnung habe, wie ich die einzelnen Zahlen mit dem Element vergleiche. Ist ja prima, dass die Zahl im ersten Label z.b. 5 ist und auch angezeigt wird, aber wie kann ich die Zahl aus diesem Label einzeln rausarbeiten . . . das sieht momentan bei mir so aus:

    public void actionPerformed(ActionEvent e)         
           {                                                   
                  if (e.getSource()==button1)                       
                  {                                            
                  for (int a=0; a<max; a=a+1)                  
                  {                                            
                  s=TF[a].getText();                          
                  a1[a]=Integer.parseInt(s1);                  
                  LA[a].setText(""+a1[a]);                     
                  }                                            
                  }                                            

                  if (e.getSource()==button2)                       
                  {                                           
                  
                  }

Ich habe zwar das ganze Theoriewissen über Quicksort und wir haben endlose Reihen von Hand sortiert, aber mit der Praxis komme ich irgendwie nicht wirklich zurecht

Vielleichten sollten Mädchen einfach die Finger von der Informatik lassen 😳 - zumindest bei mir ist logisches Denken nicht so die Stärke 🙁

 

[Der Müde Joe]

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

hoffe dies hilft

EDIT:
by the way: Text rauslesen mit getText(); siehe
http://java.sun.com/javase/6/docs/api/javax/swing/JLabel.html

und halt in ein Array Liste oder so was packen

 

[Jah]

Leider komme ich damit auch nicht so wirklich klar, da ich die einzelnen Zeilen nicht nachvollziehen kann. Gibt es den Quicksort-Alogrithmus eigentlich irgendwo auch komplett erklärt zu "lesen"
Mir fällt es einfach schwer, mich in andere Programme zu lesen und dann kann ich Teile des Programm nicht mal für mich selbst erklären oder weiß nicht, woher einige Dinge da kommen.
Trotzdem danke für die Hilfe.

 

[Der Müde Joe]

naja....da gehen mir bald die links aus....google..google...wiki?

http://de.wikipedia.org/wiki/Quicksort
http://www.linux-related.de/coding/sort/sort_quick.htm

wobei die Methode von der FH Flensburg ja eigentlich sehr gur erklärt..finde ich

1. wähle das mittlere Element der Folge als Vergleichs­element x;

setze i = 0 und j = n-1;

wiederhole solange i<=j
1. suche von links das erste Element ai mit ai>=x;

suche von rechts das erste Element aj mit aj<=x;

falls i<=j
1. vertausche ai und aj;

setze i = i+1 und j = j-1;

 

[Saxony]

Hiho,

also für die Recherche kann man auch immer mal bei GoogleCodeSearch vorbei schauen. 😀

http://www.google.com/codesearch

bye Saxony

 

[Jah]

naja....da gehen mir bald die links aus....google..google...wiki?

http://de.wikipedia.org/wiki/Quicksort
http://www.linux-related.de/coding/sort/sort_quick.htm

wobei die Methode von der FH Flensburg ja eigentlich sehr gur erklärt..finde ich

1. wähle das mittlere Element der Folge als Vergleichs­element x;

setze i = 0 und j = n-1;

wiederhole solange i<=j
1. suche von links das erste Element ai mit ai>=x;

suche von rechts das erste Element aj mit aj<=x;

falls i<=j
1. vertausche ai und aj;

setze i = i+1 und j = j-1;

Das Pivot-problem habe ich glaube ich gelöst (ich setze das alte Element einfach + bzw - 1 (je nachdem welches Feld)
Und heute glaube ich auch endlich die Erklärung zu verstehen, die du in deinem Posting hast.
Ich habe jetzt die Zeiger so gesetzt i=0 und j=max (bin mir hier aber nicht sicher, ob das nicht max-1 sein muss (max definiert die Anzahl der Textfelder und damit die Anzahl der Zahlen))

Dann habe ich eine while-schleife im zweiten button (siehe oben) begonnen . . . diese heißt while(i<=j)
Aber wie "suche" ich nun das erste Element von links bzw. rechts heraus, um es mit dem Pivot-Element zu vergleichen?

 

[Jah]

Oder die Frage vielleicht noch anders (^^): Wie kann man diese Zeiger auf eine einzelne Zahl aus dieser Reihe setzen und diesem "Zeigen" Anweisungen geben?
Mein Problem ist halt einfach, dass wir im Stoff nie so richtig sinnvoll vorwärts gekommen sind und ich absolut kein Ahnung habe, wie das mit den Zeigern programmiertechnisch irgendwie funktionieren soll.

Das Tauschen von Werten ist ja kein Problem, aber bei diesen Zeigern...

Auf alle Fälle müsst ich eine If-Schleife beginnen, um die Zahlen mit der Pivotelement zu vergleichen bzw. sie später auch zu tauschen denke ich.

Also so sinngemäß: Wenn Wert a kleiner als pivot dann rücke Zeiger einen nach rechts (i+1) ansonsten tausche mit dem nächsten Element des Zeigers j, dass seinerseits kleiner ist als pivot

also vielleicht so in der Art

if(i<pivot){i+1; else{tausche();}} tausche() sollte dann weiter unten noch definiert werden, aber das ist ja nun nicht das große Problem denke ich.

Mein Problem ist einfach, dass ich nur ein Textfeld definiert habe (so muss es sein) und es dann über die Variable max verfielfacht habe . . . nun werden die vielen Textfelder gefüllt, aber ich komme einfach nicht dahinter, wie ich dann z.B. sagen kann: "Wähle Zahl aus Label "oben" und vergleiche".

lg