✔ QuickSort

[illaX]

Hi, ich habe ein Problem mit QuickSort

private int sortierung[] = {1,3,3,1,3,3,1,1,3,1,5};
Ausgabe:
5
3
3
3
3
3
1
1
1
1
1

wenn ich jetzt die fünf nicht im Array steht
Ausgabe:
3
3
1
3
3
3
1
1
1
1
das ist nicht mehr wirklich sortiert oder?

Hier ist mein code, vllt. kann mir ja jemand helfen:

public class QuickSort
{
    private int sortierung[] = {1,3,3,1,3,3,1,1,3,1};
    
    /**
     * 
     */
    public QuickSort()
    {
        super();
        // TODO Auto-generated constructor stub
        sortieren(0, sortierung.length-1);
    }
    
    public void sortieren(int y, int z)
    {      
        int i = y;
        int j = z;
        int x = sortierung[(y+z)/2];
        
        //Aufteilung
        while(i <= j)
        {
            while(sortierung[i] > x)
            {
                i++;
            }
            while(sortierung[j] < x)
            {
                j--;
            }
            if(sortierung[i] <= sortierung[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 = sortierung[i];
        sortierung[i] = sortierung[j];
        sortierung[j] = tmp;
    }
    public void ausgeben()
    {
        for(int i = 0; i < sortierung.length; i++)
        {
            System.out.println("" + sortierung[i]);
        }
    }
    public static void main(String args[])
    {
        QuickSort s1 = new QuickSort();
        s1.ausgeben();
    }
}

und vielen dank für jede Hilfe!

 

[Snape]

Tach,
liefert Arrays.sort(sortierung); auch ein falsches Ergebnis?

 

[Thomas Darimont]

Hallo,

Arrays.sort liefert wohl das "richtige" Ergebnis, jedoch verwendet Arrays.sort() keinen Quicksort sondern einen mergsort Algorithmus.
@OP schau dir einfach eine der Zahlreichen Beispiele zum Quicksort an und schau nach wo du vielleicht was falsch abgetippt hast...

Gruß Tom

 

[illaX]

Arrays.sort(sortierung); funktioniert, aber ich möchte es gerne selber programmieren. Kannte diese Funktion noch nicht, danke

ich habe mir schon mehrere Beispiele angeguckt und finde meinen "abgetippten" Fehler nicht. Was meinst du wohl warum ich euch Frage?

Ich hoffte auf eine Erklärung und nicht auf...

MfG
illaX

 

[cham]

Ich hatte gerade mal Zeit, aber eigentlich ist das schon ein easy Beispiel. Keine Ahnung was Du da gebaut hast, aber so gehts:

public class Quicksort
{
    private int sortierung[] = {1,3,5,3,1,3,3,1,9,1,3,1,8};
    
    public Quicksort()
    {
        super();
        sortieren();
    }
    
    public void sortieren()
    {      
        //Aufteilung
        for (int i = 0; i < sortierung.length - 1;)
        {
            int y = sortierung[i];
            int z = sortierung[i + 1];
            
            System.out.println("compare: " + y + " with  " + z);
            
            if(sortierung[i] > sortierung[i + 1])
            {
                System.out.println("bigger");
                
                sortierung[i] = z;
                sortierung[i + 1] = y;                
                
                i--;
            }
            else
            if(sortierung[i] < sortierung[i + 1])
            {
                System.out.println("lesser");
                
                i++;
               
            }
            else
            if (sortierung[i] == sortierung[i + 1]){
                
                System.out.println("the same");
                i++;
                
            }
            System.out.println("--------------------------------------");
        }
        
    }
    
    public void exchange(int i, int j)
    {
        int tmp = sortierung[i];
        sortierung[i] = sortierung[j];
        sortierung[j] = tmp;
    }
    public void ausgeben()
    {
        System.out.print("Sorted: ");
        
        for(int i = 0; i < sortierung.length; i++)
        {
            System.out.print(sortierung[i]);
            
            if(i < sortierung.length - 1){
                System.out.print(",");
            }
            
        }        
    }
    public static void main(String args[])
    {
        Quicksort s1 = new Quicksort();
        s1.ausgeben();
    }
}

mit ein paar zusätzlichen Ausgaben hätten Dir es wohl erlaubt selbst drauf zu kommen...

 

[illaX]

vielen dank, tut mir leid das ich euch damit vllt. genervt habe.

MfG
illaX

 

[cham]

Mir fällt aber nochwas auf. War Quicksort nicht die Sortierung mit der Halbierung der Werte?

 

[Warhamster]

Ein Element nehmen.
Alle Elemente die größer sind auf die rechte Seite, alle die kleiner sind auf die linke.
Verfahre nun genauso mit der linken und rechten Seite bis man keine linke und Rechte Seite mehr bilden kann.

 

[illaX]

richtig

 

[illaX]

hoho ich habe meinen Fehler gefunden.

//Aufteilung
        while(i < j)                           <-- dort hatte ich <= 
        {
            while(sortierung[i] > x)
            {

vielen dank für eure Hilfe.

MfG
illaX