Answer the following questions What does it mean for a sorti

Answer the following questions. What does it mean for a sorting algorithm to be \"stable\"? Name a stable and a non-stable sorting algorithm. Explain the key reasons for an algorithm to be stable or not stable. What does it mean for a sorting algorithm to be \"in-place\"? Name an in-place and a non-in-place sorting algorithm. Explain the key reasons for an algorithm to be in-place or non-in-place.

Solution

a) The sorting algorithm is said to be stable if two objects with equal keys appear in the same relative order in the output order as they appear in the input order.
Example:
input order:apple grape banana pineapple blueberry
Output order: apple banana blueberry grape pineapple

sorting based on first letter of the word , stable algorithm will kepp the relative position of banana and blueberry as they appear in the input.

Following are the examples of stable sorting algorithm:
Selection sort,
Merge sort
Bubble sort etc.

Following are the examples of stable sorting algorithm:
Heap sort
Shell sort etc

Reason of being stable or non-stable depends on the comparisons and swapping that the algorithm uses. If the comparison and swap occur between far-slung objects in the array without looking at the elements in between first then the sort will be non-stable.

b) in-place algorithm is the algorithm which transforms the input using auxillary data structure,however the small amount of extra storage space is allowed for auxillary variables.
The input is generally overwritten by the output as the algorithm executes.
In-place algorithm replaces input sequence only by swapping or replacement of the input elements

Following are the examples of in-place algorithms
Selection sort
Insertion sort
Bubble sort etc.

Following are the examples of non in-place algorithms
Merge sort

Reason for being in-place or non in-place algorithm is specified in the definition itself.