Algoritmo in loco

Da Wikipedia, l'enciclopedia libera.

Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di informatica, vedi la relativa categoria.

Un algoritmo si dice in loco, o in place dall'inglese, quando non alloca memoria al di fuori del proprio ambiente locale.

In pratica, una funzione che accetta n parametri e che crea m variabili locali è in loco perché sia i parametri che le variabili locali risiedono sullo stack, non richiedendo quindi al processo di chiedere al sistema operativo l'allocazione di ulteriore memoria.

Gli algoritmi in loco sono più efficienti in termini di memoria e, spesso, anche in termini di CPU, rispetto alle controparti non in loco e tendono quindi ad essere preferiti rispetto a questi ultimi.

[modifica] Alcuni algoritmi in loco

Ecco una serie di algoritmi di ordinamento che operano in loco:

• Bubble sort
• Insertion sort
• Quicksort
• Selection sort
• Integer sort. Ha anche una controparte non in loco, leggermente più efficiente in termini di CPU ma con la stessa complessità (lineare)
• Heap sort
• Shell sort