Objektarrays sortieren

[Cheefrocker]

Hallo zusammen!

Ich habe ein Array von Objekten. Wie kann ich dieses Array am schnellsten Sortieren? Sortiert wird nach einer Variable die sich im Objekt befindet.

Besten dank für alle!


Kann ich hier quicksort einsetzen??


Folgender Code scheint nicht richtig zu klappen und dauert viel zu lange wenn er mal durchläuft.

/*
 * QuickSorter.java
 *
 * Created on 19. September 2007, 09:34
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package universal;
import EDA_LN.dataobject;

//Sortier 
public class QuickSorter2
{
    private Object[] a;
    private int n;

    public void sort(Object[] a)
    {
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
    }
    public void output()
    {
        for(int i=0;i<a.length;i++)
            System.out.println(((dataobject)a[i]).getmitgliedsnr());
    }

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

        //  Aufteilung
        while (i<=j)
        {    
            while (Integer.parseInt(((dataobject)a[i]).getmitgliedsnr())<Integer.parseInt(((dataobject)x).getmitgliedsnr())) i++; 
            while (Integer.parseInt(((dataobject)a[i]).getmitgliedsnr())>Integer.parseInt(((dataobject)x).getmitgliedsnr())) 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)
    {
        Object t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class QuickSorter

 

[maki]

Am schnellsten + einfachsten wäre:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html#sort(T[],%20java.util.Comparator)

Arrays.sort( deinArray, deinComperator );

 

[Cheefrocker]

Ist er denn Schneller als folgende Variante

public class FileSorter {
  
   //Sortiert die Collection nach String, gibt die sortierte collection als Array zurück
  public static Object[] sort(Collection Input) 
   { 
    Object[] output = Input.toArray();            
                  
            for(int i = output.length - 1; i > 0; i--) 
            { 
                 for(int j = 0; j < i; j++) 
                 { 
                     if((((dataobject)output[j]).getmitgliedsnr().compareTo(((dataobject)output[j + 1]).getmitgliedsnr())) > 0)
                     { 
                         Object neu =output[j];
                         output[j] = output[j+1];
                         output[j+1] = neu;
                     } 
                 } 
             } 
            
     return output;
}   
}

 

[maki]

Ist er denn Schneller als folgende Variante

Möchtest du wissen, ob ein Bubblesort schneller ist als ein Mergesort?
Meistens nicht, kommt aber auf die Daten an.

 

[Cheefrocker]

ein quicksort ist dann hier nicht möglich?

 

[SlaterB]

wer sagt das?
doch, Quicksort ist auch hier (was immer das ist, im Grunde ja überall) möglich

 

[Gast]

KÖnnte mir einer von euch ein lauffähigen Quicksort als Quellcode geben?

 

[maki]

Einen?

http://www.esus.com/javaindex/pcalgorithms/algorithms/sortingsearching/quicksort.html

google ist dein Freund...

 

[tfa]

KÖnnte mir einer von euch ein lauffähigen Quicksort als Quellcode geben?

Warum willst Du das unbedingt selber machen? Was ist schlecht an Arrays.sort()? (siehe maki)

tfa

 

[Gast]

es ist nicht schlecht, aber brauch ein möglichst schneller algorithmus!

Muss mehr als 10000 Werte untereinander vergleichen! Bei Bubblesort dauert es etwas lange.

 

[tfa]

Arrays.sort() verwendet ein modifiziertes Mergesort mit garantierter Laufzeit O(n)=n*log(n). Schneller
geht es nicht.
Quicksort kann -- wenn man Pech hat -- zu O(n)=n² entarten.

 

[cheefrocker2]

Alles werde es so verwenden. Danke euch!

 

[byte]

Hier ist beschrieben, wie es noch ein wenig schneller geht.

 

[Gelöschtes Mitglied 5909]

www.sortieralgorithmen.de

 

[Professor Chaos]

Arrays.sort() verwendet ein modifiziertes Mergesort mit garantierter Laufzeit O(n)=n*log(n). Schneller
geht es nicht.
Quicksort kann -- wenn man Pech hat -- zu O(n)=n² entarten.

Ich weiß, dass ich mich mit diesem Post unbeliebt mache.^^
Ich selbst mag auch keine Besserwisser, ich hoffe aber dennoch, dass ihr gnädig mit mir umgeht. Ich bin nämlich leider ein Perfektionist und muss daher einfach den folgenden Kommentar loswerden:

"O(n)=n*log(n)" macht genauso wenig Sinn wie "O(n)=n²". Was du, tfa, meintest, war O(f)=n*log(n), bzw. O(f(n))=n*log(n). (Okay, ganz formal gesehen müsste man Element-aus-Zeichen verwenden, aber das wäre viel zu überformal.) Was wohl noch einfacher (da weniger formal) wäre, wäre auf das Istgleich gänzlich zu verzichten, also nur die Klasse O(f) anzugeben (siehe unten, "noch einfacher"). Ich störe mich nur daran, dass auf der einen Seite O(n) steht und auf der anderen Seite eine Funktion, die Definitiv nicht in die Klasse O(n) gehört.

Richtig wäre also:
Mergesort hat garantierte Laufzeit von O(f)=n*log(n), und
Quicksort hat WorstCase Laufzeit O(f)=n².

oder noch einfacher ausgedrückt:

Mergesort hat garantierte Laufzeit von O(n*log(n)), und
Quicksort hat WorstCase Laufzeit O(n²).


Sorry für diese Kleinlichkeit...

 

[Marco13]

Warum solltest du dich (bei mir) unbeliebt machen, wenn du (mir) Arbeit ersparst?

 

[xdavidx]

Quicksort hat zwar einen WC von €O(n²) der kann aber fast ausgeschlossen werden wenn man das sog. Pivot geschickt wählt UND eine geschickte Vertauschung von Container Ende, Anfang, Mitte bei jedem Rekursionsaufruf durchführt => €O(n*lon n) ohne WC Risiko!

Quicksort ist in der Praxis fast immer schneller als Mergesort.

http://www.inf.ethz.ch/personal/staerk/algorithms/SortAnimation.html

 

[tfa]

Quicksort ist in der Praxis fast immer schneller als Mergesort.

Quicksort ist leider nicht stabil und deswegen für viele Anwendungsfälle ungeeignet.

 

[xdavidx]

Quicksort ist in der Praxis fast immer schneller als Mergesort.

Quicksort ist leider nicht stabil und deswegen für viele Anwendungsfälle ungeeignet.

Wie meinst du das?

 

[SlaterB]

http://www.google.de/search?hl=de&q=Sortieralgorithmen+Stabilität&meta=

 

[SchonWiederFred]

while (Integer.parseInt(((dataobject)a[i]).getmitgliedsnr())<Integer.parseInt(((dataobject)x).getmitgliedsnr())) i++; 
while (Integer.parseInt(((dataobject)a[i]).getmitgliedsnr())>Integer.parseInt(((dataobject)x).getmitgliedsnr())) j--;

Das ständige Parsen bremst den eigentlichen Sortiervorgang enorm aus. Wenn die Mitgliedsnummer als String in einem Format vorliegt, dass garantiert in einen Integer geparst werden kann, wieso speicherst Du sie dann nicht von vornherein als int? Damit wirst Du den Sortiervorgang nach meiner Einschätzung um einen großen Faktor beschleunigen können.

Außerdem ist der Name "dataobject" nicht besonders aussagekräftig. Da ein dataobject eine Mitgliedsnummer hat, solltest Du die Klasse vielleicht in "Mitglied" oder einen anderen sprechenden Namen umbenennen.

Wenn Du das Array statt Object[] als Mitglied[] deklarierst, kannst Du Dir das ganze Gecaste sparen. Und für den Comparator verwenden wir Generics, dann brauchst Du dort auch nicht casten.

Also:

class Mitglied
{
	private int mitgliedsnr;
	private String name;
	
	public Mitglied(int mitgliedsnr, String name)
	{
		this.mitgliedsnr = mitgliedsnr;
		this.name = name;
	}
	
	public int getmitgliedsnr()
	{
		return mitgliedsnr;
	}
	
	public String toString()
	{
		return name + ", " + mitgliedsnr;
	}
}

public class QuickSorter2
{
	public static void sort(Mitglied[] mitglieder)
	{
		java.util.Arrays.sort(mitglieder, new java.util.Comparator<Mitglied>()
		{
			public int compare(Mitglied a, Mitglied b)
			{
				return a.getmitgliedsnr() - b.getmitgliedsnr();
			}
		});
	}
}

Der Trick mit der einfachen Subtraktion in der compare-Methode funktioniert nur, wenn Mitgliedsnummern nicht negativ sind, aber davon kann man wohl ausgehen.