In-place algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     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[0..n-1])
     for i from 0 to floor((n-2)/2)
         temp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := 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[editovat | editovat zdroj]

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 konstatntě tři proměnné
  • Heapsort - Je in-place. K práci potřebuje konstatntní množství paměti.
  • Quicksort - Není in-place. Ač se jedná o jeden z nejefektivnějšícjch algoritmů, potřebuje v průměrném případě O(log(n)) místa paměti.