Selection sorts array by repeatedly finding minimum element and placing it in the starting point of loop. Starting point moves to right, incrementing it by 1.

To the left of the starting point is the sorted subarray. To the right of the starting point is the unsorted subarray.

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

• The subarray which is already sorted.
• Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

How selection sort works?

Selection Sort Algorithm - Java Implementation

Selection Sort Algorithm - Python Implementation

Complexity Analysis of Selection Sort:

Time Complexity: The time complexity of Selection Sort is O(N2) as there are two nested loops:

One loop to select an element of Array one by one = O(N) Another loop to compare that element with every other Array element = O(N) Therefore overall complexity = O(N)O(N) = O(NN) = O(N2)

Auxiliary Space: O(1) as the only extra memory used is for temporary variable while swapping two values in Array. The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Is Selection Sort Algorithm stable? Stability : The default implementation is not stable. However it can be made stable.

Is Selection Sort Algorithm in-place? Yes, it does not require extra space.

Program to sort an array of strings using Selection Sort

Selection Sort Strings - Java Implementation

Selection Sort Strings - Python Implementation

Time Complexity: O(n2), where n represents the size of the character array. Auxiliary Space: O(100), no extra space is required, so it is a constant.

Stable Selection Sort

A sorting algorithm is said to be stable if two objects with equal or same keys appear in the same order in sorted output as they appear in the input array to be sorted. Any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal key or by tweaking it in a way such that its meaning doesn’t change and it becomes stable as well. Example :

Note: Subscripts are only used for understanding the concept.

Input : 4A 5 3 2 4B 1 Output : 1 2 3 4B 4A 5

Stable Selection Sort would have produced Output : 1 2 3 4A 4B 5

Selection sort works by finding the minimum element and then inserting it in its correct position by swapping with the element which is in the position of this minimum element. This is what makes it unstable. Swapping might impact in pushing a key(let’s say A) to a position greater than the key(let’s say B) which are equal keys. which makes them out of desired order. In the above example 4A was pushed after 4B and after complete sorting this 4A remains after this 4B. Hence resulting in unstability. Selection sort can be made Stable if instead of swapping, the minimum element is placed in its position without swapping i.e. by placing the number in its position by pushing every element one step forward. In simple terms use a technique like insertion sort which means inserting element in its correct place.

EXPLANATION WITH EXAMPLE:

Example: 4A 5 3 2 4B 1 First minimum element is 1, now instead of swapping. Insert 1 in its correct place and pushing every element one step forward i.e forward pushing. 1 4A 5 3 2 4B Next minimum is 2 : 1 2 4A 5 3 4B Next minimum is 3 : 1 2 3 4A 5 4B Repeat the steps until array is sorted. 1 2 3 4A 4B 5

Reference:

https://www.geeksforgeeks.org/selection-sort/?ref=lbp https://www.geeksforgeeks.org/program-to-sort-an-array-of-strings-using-selection-sort/ https://www.geeksforgeeks.org/stable-selection-sort/