Symulacja interaktywna - Zintegrowana Platforma Edukacyjna

1

Polecenie 1

Za pomocą symulacji interaktywnej porównaj ze sobą (pod kątem złożoności) omawiane w e‑materiale algorytmy sortowania, a następnie wykonaj polecenia.

Zastanów się, jak zdefiniować poszczególne scenariusze.

RvrZi4woWZIwS

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Poniżej przedstawiono 4 tabele porównujące algorytmy sortowania.

Sortowanie kubełkowe
Złożoność czasowa			Złożoność pamięciowa
Scenariusz optymistyczny	Scenariusz oczekiwany	Scenariusz pesymistyczny	Scenariusz pesymistyczny
$O(n + k)$	$O(n+\frac{n^2}{k}+k)$	$O(n^2)$	$O(n+k)$

Sortowanie bąbelkowe
Złożoność czasowa			Złożoność pamięciowa
Scenariusz optymistyczny	Scenariusz oczekiwany	Scenariusz pesymistyczny	Scenariusz pesymistyczny
$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$

Sortowanie przez zliczanie
Złożoność czasowa			Złożoność pamięciowa
Scenariusz optymistyczny	Scenariusz oczekiwany	Scenariusz pesymistyczny	Scenariusz pesymistyczny
$O(n+r)$	$O(n+r)$	$O(n+r)$	$O(n+r)$

Sortowanie szybkie
Złożoność czasowa			Złożoność pamięciowa
Scenariusz optymistyczny	Scenariusz oczekiwany	Scenariusz pesymistyczny	Scenariusz pesymistyczny
$O(n\log(n))$	$O(n\log(n))$	$O(n^2)$	$O(n\log(n))$

Polecenie 2

RVuE0lUqtbTCc

Polecenie 3

RZn3Vh8PvMpae