CODEWITHSUNDEEP
algorithmsorting
RoarG
RoarG

Reputation: 823

Is stable and in-place the same?

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?

Upvotes: 2

Views: 10749

Answers (4)

Ayush chanchal
Ayush chanchal

Reputation: 1

No, Both are different Stable- It gives the order to each element in an array it means if there are two elements of same value then after sorting the element between those two same elements which appear first in unsorted array will be write ahead of another same element in the sorted array. Eg:- array={10,1,1',2} After sorting array={1,1',2,10}

In Place- in sorting when we don't need any additional array to sort an array. Eg:- bubble sort, insertion sort etc.

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

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.

Upvotes: 6

Potatoswatter
Potatoswatter

Reputation: 137810

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.

Upvotes: 3

Jon
Jon

Reputation: 437376

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).

Upvotes: 2

Related Questions