QuickSort mit 2 Kriterien durchführen

[Guest]

Hi All,

ich habe 2 Arrays(eindimensinal) und muss wissen welche Werte nicht in den Arrays doppelt sind, um mit diesen weiterzuarbeiten. Dazu packe ich beide Arrays in eins. Jedes Array hat ein unterKriterium, falls das erste gleich ist. Diese wollte ich dann über Quicksort sortieren. Nun könnte ich. Immer Wertpaar 1 mit Wertpaar 2 vergelcihen, sind diese gleich, dann egal, sonst merke dir diesen Wert.

Ablauf:

z.B Aufbau Array1: 1|3 | 2|2 | 2|5 | 1|4
z.B Aufbau Array1: 1|3 | 2|2 | 2|3 | 1|4


es stehen also 4 Wertpaare jeweils drin. Der 1. Wert ist immer das Hauptkriterium, und der 2. Wert immer das danach zu sortierende, wenn das 1. gleich ist.

Nun bastel ich diese über arraycopy in ein zwischenfeld, das dann so aussieht.

zwischenfeld: 1|3 | 2|2 | 2|5 | 1|4 | 1|3 | 2|2 | 2|3 | 1|4

Quicksort soll dann ergeben:

1|3 | 1|3 | 1|4 | 1|4| 2|2 | 2|2 | 2|3 | 2|5

------------

Kennt jemand eine Möglichkeit wie dies geht???? Steige irgendwie nicht mehr durch.

Gibt es vielleicht gar eine andere Variante wie man eleganter an die Wert 2|3 und 2|5 rankommt?

Ich bedanke mich für eure Hilfe.

 

[Bert Brenner]

Mir ist noch nicht ganz klar wie deine Datenstrukturen aussehen,

vielleicht sollte man die Wertepaare in einer Klasse kapseln die dann auch gleich Comparable implementiert.

 

[Gast]

Wie könnte sowas aussehen? Bin leider nicht so tief in der Materie ;-(

Danke

 

[KSG9|sebastian]

public class Wertepaar implements Comparable{
    private int wert1, wert2;

    //nötige Methoden aus dem Interface Comparable implementieren

}

 

[Gast]

Erstmal danke.

Dies läuft doch am Ende darauf hinaus, das ich jedes mal wert1 von Array 1 mit wert1 aus Array 2 vergleiche, dann wieder wert1 aus Array 1 mit Wert2 aus Array 2 vergleiche. Und so muss ich mich dann durchkämpfen, bis ich jedes Element von Array 1 mit Array2 verglichen habe und umgekehrt.

Darauf läuft diese Variante hier doch raus, oder? Braucht dies nicht wesentlich länger, als alles in 1 array zu basteln, dieses dann zu sortieren und dann einmal von vorne nach hinten durchzugehen?


Ich seh mir erstmal das Comparable genauer, mal sehen was das alles kann.

Noch weitere Ansätze? ;-)

 

[Bert Brenner]

Ich würd ja vielleicht ne bessere Lösung posten können, poste doch mal was du im augenblick hast.

 

[KSG9|sebastian]

Das was du beschreibst hört sich recht komisch an..wie sieht dein array genau aus? So vielleicht?


array[0] = 1|2
array[1] = 3|4

oder so

array[0] = 1 //Das ist ein
array[1] = 2 //Wertepaar
array[3] = 3

 

[Guest]

array[0] = 1 //Das ist ein
array[1] = 2 //Wertepaar

so ist dies gemacht, so muss ich immer nur immer in Schleifen darauf achten, das ich nicht durcheinander komme. Dies ist nicht weiter wild.





so erstmal ein free-quicksort: lo0 = anfangsindex von übergebene zu sortierenden Feld und hi0 der letzte
------------------------------------------------------------------
private static int[] quickSort(int a[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
int mid;

if ( hi0 > lo0)
{

/* Arbitrarily establishing partition element as the midpoint of
* the array.
*/
mid = a[ ( lo0 + hi0 ) / 2 ];

// loop through the array until indices cross
while( lo <= hi )
{
/* find the first element that is greater than or equal to
* the partition element starting from the left Index.
*/
while( ( lo < hi0 ) && ( a[lo] < mid ) )
++lo;

/* find an element that is smaller than or equal to
* the partition element starting from the right Index.
*/
while( ( hi > lo0 ) && ( a[hi] > mid ) )
--hi;

// if the indexes have not crossed, swap
if( lo <= hi )
{

//swap them around
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;

++lo;
--hi;
}
}

/* If the right index has not reached the left side of array
* must now sort the left partition.
*/
if( lo0 < hi )
quickSort( a, lo0, hi );

/* If the left index has not reached the right side of array
* must now sort the right partition.
*/
if( lo < hi0 )
quickSort( a, lo, hi0 );
}
return a;
}

------------------

Jetzt das relevante Zeugs aus der main:

int Trennstelle=3; //sagt quasi nehme aus diesen Felder jeweils die ersten 4 Element
int []zusammenfass=new int [(Trennstelle+1)*2];
//von Feld1 und Feld2


//clonen : b = a.clone();
System.arraycopy(Feld1, 0, zusammenfass, 0, Trennstelle+1);
System.arraycopy(Feld2, 0, zusammenfass, Trennstelle+1, Trennstelle+1);
System.out.println("--");

Test.quickSort(zusammenfass, 0, 7);

---------------------

werde jetzt erstmal das Quicksort umarbeiten, damit dann immer 2 Stellen als 1 betrachtet werden, denke mal einfach am Zähler rumpfuschen.

Danach werde ich dann wohl auf die ungerade Stellen quicksort jagen in den Bereichen wo die Geraden stellen gleich sind.

Weiss noch nicht genau wie, aber gefällt mir eigentlich noch gar nicht so recht.

----------------------

Notfalls baue ich auch gerne die Datenstruktur um, hauptsache dies läuft ziemlich zackig ab. Schon das arracopy kommt mir sehr lahm vor ;-(

--------------------

Idee ;-)

 

[Bert Brenner]

Ich denk mal so kommt das nicht in Frage oder?

import java.util.*;


public class Wertepaar implements Comparable {
  int wert1;
  int wert2;
  
  
  
  public Wertepaar(int wert1, int wert2) {
    this.wert1=wert1;
    this.wert2=wert2;
  }
  
  
  
  public int compareTo(Object o){
    Wertepaar other = (Wertepaar)o;
    
    if (this.wert1 < other.wert1)
      return -1;
    
    if (this.wert1 > other.wert1)
      return 1;
    
    if (this.wert1 == other.wert1){
      if (this.wert2 < other.wert2)
        return -1;
      if (this.wert2 > other.wert2)
        return 1;
    }
    
    return 0;
  }
  
  
  
  public String toString(){
    return wert1+"::"+wert2;
  }



  public static void main(String[] args) {
    long time = System.currentTimeMillis();
    ArrayList wp1 = new ArrayList();
    wp1.add(new Wertepaar(1,3));
    wp1.add(new Wertepaar(2,2));
    wp1.add(new Wertepaar(2,5));
    wp1.add(new Wertepaar(1,4));
    
    ArrayList wp2 = new ArrayList();
    wp2.add(new Wertepaar(1,3));
    wp2.add(new Wertepaar(2,2));
    wp2.add(new Wertepaar(2,3));
    wp2.add(new Wertepaar(1,4));
    
    ArrayList result = new ArrayList();
    result.addAll(wp1);
    result.addAll(wp2);
    Collections.sort(result);
    
    for (int i = 0; i < result.size(); i++) {
      System.out.println (result.get(i));
    }
    System.out.println("Dauer(ms): "+(System.currentTimeMillis()-time));
  }
}

Das hier läuft jedenfalls ziemlich schnell.



Wenn du dein QuickSort benutzen möchtest, kannst du Objekte der Klasse Wertepaar einfach miteinander vergleichen.

int i = wertepaar.compareTo(wertepaar2);

i ist
-1 : wertepaar war kleiner wie wertepaar2
0 : wertepaar war gleichgross wie wertepaar2
1 : wertepaar war grösser wie wertepaar2

 

[Guest]

Sieht gut aus, mit arraylist hatte ich auch schon geliebäugelt. Jedoch traute ich mich da noch nicht so ran.

Werde es mir mal zu Gemüte ziehen und sehen ob ich das drumherum vom Prog an diese Datenhaltung anpassen kann.

Gebe dann morgen nochmal Laut von mir. Erstmal herzlichen Dank

 

[Guest]

Aber doch noch eine Frage.

Beim Debuggen ist mir aufgefallen er legt die Werte immer beim Arraylistfeld in dieser Form ab: 1::3

Sind das jetzt noch normale Werte mit denen ich rechnen kann??? Also z.B 1+3 oder muss ich die jetzt erst wieder in int konvertieren?

Da müsste man eigentlich nur in der Ausgabe Prozedur rumpfuschen wo:

public String toString(){
return wert1+"::"+wert2;
}

steht.

Und diese also durch etwas anderes ersetzen, oder? Also das dort z.B. toInt steht oder so (Integer muss man ja auch erst noch konvertieren)

Doch etwas verwirrender als ich dachte :?

Ich glaubs ich lass es erstmal sacken, drucke noch was zu arraylist aus, und dann geht weiter ;-) (morgen)

Thanks nochmal

 

[Bert Brenner]

Ups, nein toString bitte nicht ändern, das hab ich hier nur verwendet wegen der einfacheren Ausgabe.

Um die Werte wiederzubekommen würde man Wertepaar zusätzliche Methoden verpassen. z.b.:

public int getWert1(){
  return wert1;
}

public int getWert2(){
  return wert2;
}

Um sie nachträglich manipulieren zu können kann man ein paar setter Methoden hinzufügen:

public void setWert1(int wert){
  wert1=wert;
}

public void setWert2(int wert){
  wert2=wert;
}

um jetzt z.b. einen Wert von einem Wertepaar aus der ArrayList zu holen muss man folgendes tun:

Wertepaar wp = (Wertepaar)result.get(2);
System.out.println("Wert1: "+wp.getWert1());
System.out.println("Wert2: "+wp.getWert2());

Hoffe das ist jetzt etwas klarer.

 

[Guest]

Merci, jetzt komme ich langsam dahinter ;-)