Fehler im Sortieralgorithmus

[Coder21]

Hallo,

ich versuche mit folgendem Algorithmus einen Vector der Größe nach zu sortieren. (Es muss aus bestimmten Gründen ein Vector sein) Irgendwo muss jedoch ein Fehler sein, da sehr vereinzelt Sortierfehler auftreten. Könnt ihr mir sagen, wo der Fehler liegt?

public Vector<Integer> getSortedVector(Vector<Integer> input)
    {
        for(int i=0;i<input.size();i++)
        {
            int s1=input.elementAt(i);
            for(int j=0;j<input.size();j++)
            {
                int s2=input.elementAt(j);
		if(s1>s2)
		{
			int tmp=input.elementAt(j);
			input.setElementAt(input.elementAt(i),j);
			input.setElementAt(tmp,i);					
		}
            }
        }
        return input;
    }

Beispiel:
Eingabe:

8;1;3;10;1;9;1;3;4;6;2;2;9;1;6;2;3;8;3;11;3;3;3;12;10;2;6;3;4;11;4;8;2;6;6;1;3;3;5;4;12;1;2;1;5;3;12;1;1;3;7;4;6;1;8;1;7;2;6;9;6;2;11;2;8;3;1;7;2;7;3;4;11;2;1;3;8;2;5;6;1;1;7;6;2;3;3;5;1;2;2;4;8;4;8;1;7;4;3;4;7;1;1;4;1;2;2;1;8;1;3;2;3;1;2;1;2;1;3;2;11;3;2;2;2;1;3;1;3;6;1;4;1;10;1;1;2;4;9;1;2;1;6;1;2;1;1;2;2;1;2;2;7;1;2;1;1;1;2;2;3;2;2;4;4;2;2;5;2;1;3;1;2;2;1;3;6;1;4;1;7;1;1;1;2;3;1;1;1;4;1;1;1;4;4;1;2;2;3;2;1;4;2;3;4;2;3;3;1;2;2;1;2;1;1;1;1;1;2;2;2;2;4;5;2;2;2;1;3;1;2;3;2;1;2;1;1;2;2;1;1;2;2;1;1;2;1;1;1;1;2;2;1;1;1;1;2;1;1;1;2;2;2;2;1;1;2;2;2;1;1;1;1;1;1;2;1;1;1;1;1;2;2;1;1;1;1;1;1;1;1;1;1;1;3;1;1;1;1;1;2;1;1;1;1;2;1;1;1;1;1;1;2;1;1;2;1;1;2;2;1;1;1;1;1;1;4;1;1;1;1;1;1;1;1;1;1;1;2;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1

Ausgabe:

12;12;12;11;11;11;11;11;10;10;10;9;9;9;9;8;8;8;8;8;8;8;8;8;7;7;7;7;7;7;7;7;7;6;6;6;6;6;6;6;6;6;6;6;6;6;5;5;5;5;5;5;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;4;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;2;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;2;1;1;1;1;1;1;1;1;1;1;1;4;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;2;1;1;1;1;1;1;1;1;1

Danke für eure Hilfe.

 

[MiDniGG]

Erst mal sollte das doch Vector<Integer> heißen, oder?! Mit int grig ich nen Fehler...

 

[Coder21]

Nur ein Tippfehler... Danke für den Hinweis.

 

[SlaterB]

funktionierende Sortieralgorithmen findet man bei google diverse,

deiner sortiert eher nichts, umso erstaunlicher, dass ein derartig gutes Ergebnis herauskommt

wenn s1 einmal mit einem s2 getauscht wurde, wieso wird dann weiter vergleichen, obwohl an der Position zu s1 inzwischen ganz was anderes steht?

 

[Coder21]

Da ist also der Fehler.
Und so funktioniert es dann auch:

public Vector<Integer> getSortedVector(Vector<Integer> input)
    {
        for(int i=0;i<input.size();i++)
        {
             for(int j=0;j<input.size();j++)
            {
               int s1=input.elementAt(i);
               int s2=input.elementAt(j);
		if(s1>s2)
		{
			int tmp=input.elementAt(j);
			input.setElementAt(input.elementAt(i),j);
			input.setElementAt(tmp,i);					
		}
            }
        }
        return input;
    }

Danke!

 

[SlaterB]

nun klappts? na immerhin,
dann bleibt nur noch die quadratische Laufzeit zu bemängeln,
bei 100 Elementen muss allein 10.000 mal 2x elementAt aufgerufen und verglichen werden usw.

andere Algorithmen sind da sparsamer, aber diese Optimierung ist vielleicht nicht so dringend

 

[faetzminator]

Quicksort ? Wikipedia als Idee (obwohl, entweder in der DE oder in der EN Version hat es einen Logikfehler im Beispielcode)

 

[Marco13]

Ganz nebenbei: Wenn du Vector verwendest, und das einen Grund hat, ist das ja schön und gut. Aber das ist KEIN Grund, die spezifischen setElementAt- usw Methoden zu verwenden. Stattdessen lieber die aus dem List-interface: set, get, ...

Und abgesehen davon...

import java.util.*;

class ListSortTest
{

    public static void main(String args[])
    {
        List<Integer> list = new Vector<Integer>();
        list.add(3);
        list.add(2);
        list.add(1);

        list = getSorted(list);
        System.out.println(list);

    }

    public static <T extends List<Integer>> T getSorted(T input)
    {
        for(int i=0;i<input.size();i++)
        {
            for(int j=0;j<input.size();j++)
            {
                int s1=input.get(i);
                int s2=input.get(j);
                if(s1>s2)
                {
                    int tmp=input.get(j);
                    input.set(j, input.get(i));
                    input.set(i, tmp);
                }
            }
        }
        return input;
    }
}

...hat das ganze sowieso nichts mit einem Vector zu tun...