# ArrayList mit quicksort sortieren



## Guest (4. Feb 2009)

hi,

wie kann man eine ArrayList mit long-Werten mittels quicksort sortieren? Gibt es da schon eine Implementation, die man nutzen kann?

gruß,
Oliver


----------



## Spacerat (4. Feb 2009)

Ist es vielleicht hilfreich von vorn herein ein TreeSet zu verwenden? Da könnte man sich das Sortieren sparen. Ansonsten...

```
TreeSet<Long> tmp = new TreeSet<Long>();
tmp.addAll(unsortedarraylist);
unsortedarraylist.clear();
unsortedarraylist.addAll(tmp);
```

mfg Spacerat


----------



## didjitalist (4. Feb 2009)

kann sein, dass Collections#sort quicksort nutzt. ist aber eigentlich auch egal, denn die methode garantiert, einen "günstigen" algorithmus zu verwenden.


----------



## tfa (4. Feb 2009)

Collections.sort() benutzt Merge-Sort. Wenn es unbedingt Quicksort sein soll, nimm Arrays.sort(long[]). Das Ergebnis ist jedenfalls das selbe.


----------



## didjitalist (4. Feb 2009)

ajo, hatte auch eher mergesort im hinterkopf. wieso solls denn unbedingt quicksort sein?


----------



## Landei (4. Feb 2009)

Das sortiert sicher gründlicher


----------



## Guest (4. Feb 2009)

Eigentlich sollte der Merge-Sort bevorzugt werden, da er eine Laufzeit von n*log(n) garantiert. Quick-Sort hingegen kann im Worst-Case eine Laufzeit von n² haben.


----------



## tfa (4. Feb 2009)

Die Implementierung von Quicksort im JDK verhindert ziemlich effektiv, dass der Worstcase eintritt.


----------



## Spacerat (4. Feb 2009)

Was das TreeSet betrifft habe ich wirklich nicht den Schimmer, welcher Algo verwendet wird. Die Elemente werden ja schon beim Hinzufügen einsortiert. "Arrays.sort()" verwendet lt. "javadoc" einen "tuned" (was immer das heisst) Quicksort. Das war mein 1. Gedanke. Den hab' ich aber verworfen, weil die unsortierte Liste dazu in ein Array gewandelt, daraufhin geleert und nach "Arrays.sort()" auf das Array wieder mit dessen werten gefüllt werden muss.

```
Long[] copy = unsorted.toArray();
unsorted.clear();
Arrays.sort(copy);
for(Long l : copy) unsorted.add(l);
```

mfg Spacerat


----------



## didjitalist (4. Feb 2009)

TreeSet täte gut daran, insertion sort zu verwenden, da es immer in eine sortierte menge einfügen muss. aber auch hier ist es im grunde egal, da das interface die höchst mögliche effizienz garantiert


----------

