Jaka jest różnica między sortowaniem zewnętrznym a sortowaniem wewnętrznym? Nie rozumiem, w jaki sposób dane wejściowe mogą być przechowywane w pamięci RAM, a które nie mają związku z algorytmem.Jaka jest różnica między sortowaniem zewnętrznym a sortowaniem wewnętrznym?
W wewnętrznym sortowaniu wszystkie dane do sortowania są przechowywane w pamięci przez cały czas, gdy sortowanie jest w toku. W zewnętrznym sortowaniu dane są przechowywane poza pamięcią (jak na dysku) i ładowane do pamięci tylko w małych porcjach. Sortowanie z zewnątrz jest zwykle stosowane w przypadkach, gdy dane nie mieszczą się całkowicie w pamięci.
W przypadku sortowania wewnętrznego można zrobić coś w rodzaju sortowania skorupowego - wystarczy uzyskać dostęp do żądanych elementów tablicy w dowolnym momencie. Nie można tego zrobić w sortowaniu zewnętrznym - tablica nie jest całkowicie w pamięci, więc nie można po prostu uzyskać dostępu do dowolnego elementu w pamięci, a dostęp do niego losowo na dysku jest zwykle bardzo wolny. Zewnętrzny algorytm sortowania musi w optymalny sposób ładować i rozładowywać porcje danych.
pamięć zewnętrzna - dostajesz części danych na raz? – committedandroider
@ committedandroid: Tak, ponieważ nie można dopasować wszystkich danych do dostępnej pamięci. – sharptooth
http://en.wikipedia.org/wiki/External_sorting –
http://en.wikipedia.org/wiki/Internal_sort –
Jeśli nie widzisz różnicy w sortowaniu w pamięci lub poza pamięcią sprawia, że nie myślisz wystarczająco mocno o tej sprawie. Proponuję napisać programy do zrobienia obu. Najpierw posortuj listę liczb całkowitych o długości 100; następnie posortuj listę liczb całkowitych działających na, powiedzmy, 4TB. –