2

When talking about algorithms. I see description of both in-place and stable sorting algorithms. Is saying a algorithm is stable the same as saying its in-place? if not what is the difference?

RoarG
  • 793
  • 1
  • 7
  • 20
  • Example - standard [quick-sort](http://en.wikipedia.org/wiki/Quick_sort) is in-place and not stable. – Bernhard Barker Dec 04 '13 at 12:35
  • I don't think quicksort is in-place, it needs O(logn) additional storage. – chill Dec 04 '13 at 13:31
  • Very nice details of *in-place* terminology [here](https://stackoverflow.com/q/2779797/465053) and [here](https://stackoverflow.com/q/16585507/465053). – RBT Feb 15 '18 at 00:25

3 Answers3

6

No,

Stable algorithm means that the relative ordering of 'equal' elements shall remain same after the algorithm is executed.

For instance, if you have an array 

{-2, 4, 5, -11, 9, -10}

and you want to sort it such that all negative elements come before the positive elements. And you want the relative ordering of -ve and +ve elements remain the same 

{-2, -11, -10, 4, 5, 9}

This is the output of a stable algorithm

As noted in the comments, in place algorithm means the algorithm does not require additional space other than the input data. The output is data occupies the same place in memory that was occupied by the input data and the input data gets destroyed.

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • In-place does not require no extra space, although using O(N) extra would often defeat the point of being in-place. And "extra" is just a relative term. – Potatoswatter Dec 04 '13 at 12:36
  • The space complexity of an in-place sort algorithm is usually O(N), because the sequence itself must be in memory. An example of an O(1) space complexity algorithm on input of size N would be a max element algorithm which examines each element in turn, but doesn't require any data structure to contain all the elements. – Potatoswatter Dec 05 '13 at 02:02
3

Stable means the order of input elements is unchanged except where change is required to satisfy the requirements. A stable sort applied to a sequence of equal elements will not change their order.

In-place means that the input and output occupy the same memory storage space. There is no copying of input to output, and the input ceases to exist unless you have made a backup copy. This is a property that often requires an imperative language to express, because pure functional languages do no have a notion of storage space or overwriting data.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
2

No, it's not the same.

A stable sort is one that, for elements that compare equal, their relative position in the sorted output is guaranteed to be the same as in the source. Contrast this with an unstable sort, in which items that compare equal will appear in the sorted result in an unpredictable order. This distinction is not important in simple cases (e.g. sorting integers), but it becomes important when the sort criteria is only part of the data that each item contains (e.g. sort colored socks by size only).

An in-place sort is one that sorts the input without requiring additional space; it is also called a "destructive" sort in that after sorting you have lost the unsorted form of the input data (it has been replaced by sorted data).

Jon
  • 428,835
  • 81
  • 738
  • 806