3
$\begingroup$

What is the meaning of in place and out place in sorting? What are the difference of two of them? Couldn't find any good explanation in the internet.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Usually it's "in-place" and "not in-place" (with or without the hyphen). $\endgroup$
    – Yuval Filmus
    Jul 7, 2018 at 19:31

3 Answers 3

Reset to default
4
$\begingroup$

In place sorting is sorting without using extra memory (mostly swapping elements till getting it right).

PS In many cases it's impossible to not use any extra memory, but usually in place sorting indicates to constant extra memory.

Improve this answer
$\endgroup$
1
$\begingroup$

An in-place sorting algorithm sorts the elements in place: that is, it needs only $O(1)$ extra space.

An out-of-place sorting algorithm needs extra space to put the elements in as it's sorting them. Usually this means $O(n)$ extra space.

Improve this answer
$\endgroup$
1
$\begingroup$

The idea of an in-place algorithm isn't unique to sorting, but sorting is probably the most important case, or at least the most well-known. The idea is about space efficiency - A sorting algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time. This was especially relevant to some devices (don't have enough space for ex. Embedded system like PDA, cellphone etc.)

The idea is to produce an output in the same memory space that contains the input by successively transforming that data (mainly by replacing) until the output is produced. This avoids the need to use twice the storage - one area for the input and an equal-sized area for the output.

A/c to Wikipedia page on in-place algorithms currently claims that an in-place algorithm can only use a constant amount - O(1) - of extra space.

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

However, all algorithms require some additional storage for working variables.

Some In-place sorting algorithms :

  • Bubble sort
  • Insertion sort
  • Selection sort
  • Merge sort (modification in implementation)
  • Quick-sort
  • Heapsort

References :

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.