✔ QuickSort

[illaX]

war wohl nur ein Fehler von vielen...

Kann man QuickSort vllt. nur in bestimmten Fällen anwenden?

MfG
illaX

 

[illaX]

so jetzt müsste es gehen

if(i <= j) <--Habe dort vorher mit den Attributen vom Array überprüft...
{
exchange(i,,j);
i++;
j--;

Ich probier es jetzt nochmal in dem ich den Array mit pseudozahlen füllen lasse

MfG
illaX

 

[Luxor]

Quicksort ist, in der Literatur(z.b. Algorithmen von Robert Sedgewick), als stabiler Algorithmus definiert, d.h. Du kannst Quicksort immer anwenden. Es gibt noch einen schnelleren aber der wird als nicht stabil eingestuft! (Deshalb hab ich mir den Namen auch nicht gemerkt)
Wenn Du Quicksort noch öfters verwenden willst kannst Du es so wie in C/C++ mit qsort() = Quicksort machen. Implementiere es so dass Du nur den Comparepart anpassen must. Der Vorteil einmal implementiert und danach nur noch den Vergleich auf den jeweiligen Datentyp/Object anpassen.


Gruß

Luxor

 

[illaX]

Vielen Dank

 

[Warhamster]

Distribution Counting mit einer Komplexität von O(N) ist der schnellste Algorithmus den es gibt. Er ist aber halt nicht stabil und kann auch nicht wirklich oft eingesetzt werden.
Die Komplexität von Quicksort ist im besten Fall O(NlogN), im schlimmsten Fall kann sie aber O(N^2) sein.
Heapsort und Mergesort garantieren eine Komplexität von O(NlogN), sind aber in der Regel doch einen kleinen Tick langsamer als Quicksort.

 

[illaX]

oki mein prodramm laeuft.

Ich veroeffentliche hier mal meinen code ^^

/*
 * Created on Mar 9, 2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package sortierung;

/**
 * @author muelbjoe
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class QuickSort
{
    private int arrlist[];
    
    /**
     * @param arrlist[]
     */
    public QuickSort(int arrlist[])
    {
        super();
        // TODO Auto-generated constructor stub
        this.arrlist = arrlist;
        sortieren(0, arrlist.length-1);
    }
    
    public void sortieren(int y, int z)
    {      
        int i = y;
        int j = z;
        int x = arrlist[(y+z)/2];            
        
        //Aufteilung
        while(i < j)
        {
            while(arrlist[i] > x)
            {
                i++;
            }
            while(arrlist[j] < x)
            {
                j--;
            }
            if(i <= j)
            {              
                exchange(i,j);
                i++;
                j--;
            }
        }
        
        //Rekursion
        if(y<j) sortieren(y,j);
        if(i<z) sortieren(i,z);
    }
    
    public void exchange(int i, int j)
    {
        int tmp = arrlist[i];
        arrlist[i] = arrlist[j];
        arrlist[j] = tmp;
    }
}

MfG
illaX