schneller Sort ?

[pete22]

Hallo,
seid 2 Monaten versuche ich mich an Java und habe mit Hilfe von ArrayList einen Sortieralgorithmus geschrieben.

[Java=42]
public static ArrayList <Integer> sort (ArrayList <Integer> array)
{
ArrayList <Integer> fertig = new ArrayList <Integer>();
while(array.isEmpty() == false)
{
fertig.add(Collections.min(array));
array.remove(array.lastIndexOf(Collections.min(array)));
}
return fertig;
}
[/Java]
In ein paar Versuchen war er schneller als Quicksort und co. Wobei die Länge der Arrays <= 1000 war. Liegt es nur an der Länge der Arrays oder ist er tatsächlich schneller als die anderen ?

 

[Kevin94]

Das kommt zum einen drauf an, was du mit den Anderen meinst und dann hängt die Geschwindigkeit dieses Algorithmuses stark von Collections.min ab(das du übrigens zweilmal aufrufst, du kannst den ersten aufruf auch in ner Variable speichern, spart Zeit). Für die Geschwindigkeit deines Algorithmuses ist auserdem die Sortierung der Elemente wesentlich entscheidend.
Ich hab zwar nicht studiert, weswegen die folgende Laufzeitanalyse auf Halbwissen basiert, aber dein Algorithmus dürfte im worst-case

((n+1)*n/2)*2+n=n^2+2n

Operationen brauchen BubbleSort hat afaik eine Laufzeit von

n*(n-1)=n^2-n

, also im worst-case weniger.
[EDIT]Wenn du allerdings den zweifachen Aufruf von Collections.min entfernst hat dein Algorithmus nur noch

((n+1)*n/2)+n=0.5n^2+1.5n

, also weniger.
OK, ich hab in dem bereich wohl doch etwas zuviel Halbwissen.[/EDIT]
Am einfachsten lässt sich das wohl testen mit einem Array in umgekehrter Reinfolge, also 0 am Ende. Ausserdem kann es bei einem so kleinen Array sein das die Genauigkeit der Systemuhr dir deine Messergebnisse verfälscht.

 

[faetzminator]

Öhm, meinst du das im Ernst ? Deine Sortiermethode hat eine Laufzeit von [c]O(n^2)[/c], genau so wie Bubblesort. Wenn du einen Quicksort o.ä. verwendest, hast du [c]O(n*log(n))[/c].