In-place algoritmus
V tomto článku se chystáme prozkoumat fascinující život In-place algoritmus, jedince, který zanechal svou stopu v průběhu historie. Od svých skromných začátků až po své nejvýraznější úspěchy byl In-place algoritmus vlivnou postavou ve svém oboru. Prostřednictvím podrobné analýzy jeho kariéry odhalíme důvody jeho úspěchu a dopad, který měl na svět kolem sebe. S hloubkovým pohledem na jeho zkušenosti, úspěchy a výzvy doufáme, že objasníme důležitost In-place algoritmus a jeho trvalé dědictví.
In-place algoritmus , někdy též in situ nebo na původním místě je algoritmus, který transformuje datové struktury za pomocí malého a především konstantního množství paměti. Předpokládá se, že veškeré zpracování dat proběhne v prostoru, kde jsou uložena vstupní data. paměťová náročnost je asymptoticky .
Opak těchto algoritmů je not-in-place nebo také out-of-place algoritmus.
Příklad
Mějme a, n – prvkové pole čísel. Úkolem je zreorganizovat pole tak, aby obsahovalo prvky v opačném pořadí. Nabízející se metodou je vytvořit pomocné pole b, v němž se postupně vytvoří reorganizovaná verze vstupního pole. Ta je pak zkopírována do původního pole a .
function reverse(a)
allocate b
for i from 0 to n – 1
b := a
return b
Tento algoritmus ale potřebuje O(n) pracovní paměti pro pole b o délce n. Proto to není in-place algoritmus.
Úlohu lze ale řešit i jinak. Veškeré změny lze provádět přímo na vstupních datech. Zde konkrétně stačí jedna pomocná proměnná, která umožní vyměňovat čísla přímo v poli.
function reverse_in_place(a)
for i from 0 to floor((n-2)/2)
temp := a
a := a
a := temp
Tento algoritmus už má jen konstantní požadavky na paměť bez ohledu na velikost vstupu. Jedná se tedy o in-place algoritmus.
Řadící algoritmy
Jednou z nejčastějších aplikací in-place algoritmů jsou algoritmy řazení. Z používaných algoritmů jsou některé in-place a jiné ne.
- Bubblesort – Je in-place. K práci potřebuje konstantně tři proměnné.
- Heapsort – Je in-place. K práci potřebuje konstantní množství paměti.
- Quicksort – Není in-place. Ač se jedná o jeden z nejefektivnějších algoritmů, potřebuje v průměrném případě O(log(n)) místa paměti.