Sortowanie quicksort

Question

Słyszałem, że quicksortem nie można posortować 1e9 i większych liczb. Czy to prawda? Jeśli tak to jakie inne szybkie sortowanie jest jeszcze dostępne.

Comments

https://en.wikipedia.org/wiki/Sorting_algorithm

Answer 1

Dla algorytmu quicksorta nie ma znaczenia, jaki typ jest sortowany.

Ma znaczenie, jakiego typu są wartości są przechowywane w sortowanym kontenerze. Zwykły 32-bitowy int ma swoje limity. Zbyt dużych wartości po prostu nie będziesz w stanie wsadzić do kontenera, zanim nawet spróbujesz przesortować.

Comments

czyli 1 miliard będę w stanie posortować i wsadzić do kontenera?

---

Zależy od typu. Do vector<char>, oczywiście nie. Zwykły 32-bitowy int ma górny limit 2 147 483 647, więc na styk. W 64-bitowym (u)int64_t (czy też long long int), bez problemu.

---

...wait, dla pewności.

czyli 1 miliard będę w stanie posortować i wsadzić do kontenera?

Masz na myśli "1 miliard" jako wartość, czy 1 miliard jako rozmiar kontenera?

---

I to i to.

---

A, no to... jak masz dość RAMu żeby Ci się zmieściło miliard liczb do posortowania w kontenerze, to też jak najbardziej się da.

---

Czyli zrobienie 1e9 miejsc w tablicy zużyło by za dużo ramu?

---

Nie, niekoniecznie.

(1e9 * 8 bajtów)/1024/1024/1024 daje 8 gigabajtów. Na maszynie z 8+GB RAMu taka pojedyncza alokacja jest jak najbardziej możliwa (ewentualnie system może mieć jakieś limity per proces lub per alokacja).

---

XD w końcu nie wiem czy te nie, niekoniecznie to ironia czy nie