in-place algorithm
An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
In more detail
Reversing a list by swapping the two ends inward, and quicksort's partition step, are in place. They save memory but modify the input, which is not always acceptable if the caller still needs the original. Python's list.sort() sorts in place, while sorted() returns a new list.
Related terms
- auxiliary space — The memory an algorithm allocates beyond the input itself, such as a temporary copy or a helper array.
- space complexity — How the extra memory an algorithm needs grows with the input size, written in the same Big O notation as time.
- quicksort — A divide-and-conquer sort that picks a pivot, partitions the items into those smaller and larger than it, and sorts each part recursively.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers