Sortowanie quicksort

pytanie zadane 28 marca 2020 w C i C++ przez wall7489 Obywatel (1,280 p.)

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.

komentarz 28 marca 2020 przez DragonCoder Nałogowiec (36,500 p.)

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

1 odpowiedź

odpowiedź 28 marca 2020 przez adrian17 Mentor (355,180 p.)
wybrane 28 marca 2020 przez wall7489

Najlepsza

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ć.

komentarz 28 marca 2020 przez wall7489 Obywatel (1,280 p.)

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

komentarz 28 marca 2020 przez adrian17 Mentor (355,180 p.)

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.

komentarz 28 marca 2020 przez adrian17 Mentor (355,180 p.)

...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?

komentarz 28 marca 2020 przez wall7489 Obywatel (1,280 p.)

I to i to.

komentarz 28 marca 2020 przez adrian17 Mentor (355,180 p.)

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.

komentarz 28 marca 2020 przez wall7489 Obywatel (1,280 p.)

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

komentarz 28 marca 2020 przez adrian17 Mentor (355,180 p.)

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).