Questions tagged [in-place]

When something happens with only a constant amount of extra space, it is said to happen in-place.

Filter by
Sorted by
Tagged with
1
vote
1answer
59 views

In-place matrix transposition using rotations

Some time ago I invented an algorithm for in-place matrix transposition using rotations. A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage ...
2
votes
0answers
32 views

In-place patching of diff between two sets?

For two ordered sets of keys Paul Heckel's diffing algorithm generates the necessary actions to transform, or patch, one set to the other. I am asking how you'd do the patching without keeping a copy ...
0
votes
0answers
327 views

Interleaving first and second half of an array of even length in place

If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$ How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$ with minimal swaps and using no additional space? I ...
5
votes
0answers
569 views

Sorting in place & stable in linear time

Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics- The algorithm runs in $O(n)$ time. The algorithm is stable. The algorithm sorts ...
1
vote
1answer
148 views

Inplace sorting of variable length records

Is there an in-place algorithm for sorting variable length records? For example a vector of arbitrary length strings. Most provided in-place algorithms assume that you can switch two elements ...
18
votes
3answers
4k views

What is the most efficient constant-space sorting algorithm?

I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions: SWAP: swap the next index with the current one; ...
4
votes
1answer
5k views

Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
3
votes
2answers
222 views

Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
4
votes
1answer
355 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
33
votes
3answers
6k views

Worst case $O(n \ln n)$ in place stable sort?

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...
62
votes
3answers
11k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...