Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"
Pamięciowa złożoność obliczeniowa
Oprócz złożoności czasowej definiuje się również złożoność pamięciową. Określa ona ilość zasobów komputera, których wymaga dany algorytmw zależności od liczby danych wejściowych. Tutaj także ma zastosowanie notacja omikron. Podczas określania złożoności algorytmu należy wziąć pod uwagę oba typy złożoności obliczeniowej.
Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe grupy:
Algorytmy sortujące w miejscu (ang. in place) - wymagają stałej liczby dodatkowych struktur danych, która nie zależy od liczby elementów sortowanego zbioru danych (ani od ich wartości). Dodatkowa złożoność pamięciowa jest klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, ponieważ mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie. Sortowanie w miejscu, jest bardzo dużą zaletą.
Algorytmy nie sortujące w miejscu - wymagają zarezerwowania w pamięci dodatkowych obszarów, których wielkość jest uzależniona od liczby sortowanych elementów lub od ich wartości. Tego typu algorytmy są zwykle bardzo szybkie w działaniu, jednakże wymagają dodatkowej pamięci. Dlatego może się okazać, iż taki algorytm nie będzie w stanie posortować dużego zbioru danych, ponieważ system komputerowy nie posiada wystarczającej ilości pamięci RAM.
