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 votes
1 answer
278 views

Is radix sort in-place or out-place?

Generally, we can implement algorithms in-place and out-of-place. However, I can't say for certain that radix sort can be implemented in both ways.
user avatar
  • 120
1 vote
1 answer
111 views

Index variable takes up log(n) space?

In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits." How does an array index ...
user avatar
  • 113
0 votes
0 answers
45 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
user avatar
0 votes
1 answer
122 views

LinkedList: Remove the kth node form the end

Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
user avatar
1 vote
1 answer
241 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 ...
user avatar
2 votes
0 answers
38 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 ...
user avatar
  • 21
0 votes
0 answers
544 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 ...
user avatar
  • 143
5 votes
0 answers
710 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 ...
user avatar
  • 1,243
0 votes
1 answer
210 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 ...
user avatar
  • 595
23 votes
3 answers
5k 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; ...
user avatar
  • 4,017
5 votes
1 answer
8k 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 ...
user avatar
3 votes
2 answers
280 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 ...
user avatar
  • 303
4 votes
1 answer
440 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 ...
user avatar
  • 22.1k
40 votes
4 answers
9k 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 ...
user avatar
  • 819
66 votes
3 answers
14k 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 $$...
user avatar
  • 6,151