Selection Sort

The selection sort enhances the bubble sort by making only a single swap for each pass through the rundown. In order to do this, a selection sort searches for the biggest value as it makes a pass and, after finishing the pass, places it in the best possible area. Similarly, as with a bubble sort, after the first pass, the biggest item is in the right place. After the second pass, the following biggest is set up. This procedure proceeds and requires n-1 goes to sort n item since the last item must be set up after the (n-1) th pass.

ALGORITHM: SELECTION SORT (A)

1. k ← length [A]
2. for j ←1 to n-1
3. smallest ←  j
4. for I ← j + 1 to k
5. if A [i] < A [ smallest]
6. then smallest ←  i
7. exchange (A [j], A [smallest])

How Selection Sort works

1. In the selection sort, first of all, we set the initial element as a minimum.
2. Now we will compare the minimum with the second element. If the second element turns out to be smaller than the minimum, we will swap them, followed by assigning to a minimum to the third element.
3. Else if the second element is greater than the minimum, which is our first element, then we will do nothing and move on to the third element and then compare it with the minimum.
   We will repeat this process until we reach the last element.
4. After the completion of each iteration, we will notice that our minimum has reached the start of the unsorted list.
5. For each iteration, we will start the indexing from the first element of the unsorted list. We will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly positioned.
   Consider the following example of an unsorted array that we will sort with the help of the Selection Sort algorithm. A [] = (7, 4, 3, 6, 5).
   A [] =

1^st Iteration:

Set minimum = 7

• Compare a₀ and a₁

As, a₀ > a₁, set minimum = 4.

• Compare a₁ and a₂

As, a₁ > a₂, set minimum = 3.

• Compare a₂ and a₃

As, a₂ < a₃, set minimum= 3.

• Compare a₂ and a₄

As, a₂ < a₄, set minimum =3.

Since 3 is the smallest element, so we will swap a₀ and a₂.

2^nd Iteration:

Set minimum = 4

• Compare a₁ and a₂

As, a₁ < a₂, set minimum = 4.

• Compare a₁ and a₃

As, A[1] < A[3], set minimum = 4.

• Compare a₁ and a₄

Again, a₁ < a₄, set minimum = 4.

Since the minimum is already placed in the correct position, so there will be no swapping.

3^rd Iteration:

Set minimum = 7

• Compare a₂ and a₃

As, a₂ > a₃, set minimum = 6.

• Compare a₃ and a₄

As, a₃ > a₄, set minimum = 5.

Since 5 is the smallest element among the leftover unsorted elements, so we will swap 7 and 5.

4^th Iteration:

Set minimum = 6

• Compare a₃ and a₄

As a₃ < a₄, set minimum = 6.

Since the minimum is already placed in the correct position, so there will be no swapping.

Complexity Analysis of Selection Sort

Input: Given n input elements.

Output: Number of steps incurred to sort a list.

Logic: If we are given n elements, then in the first pass, it will do n-1 comparisons; in the second pass, it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of comparisons can be found by;

Therefore, the selection sort algorithm encompasses a time complexity of O(n²) and a space complexity of O(1) because it necessitates some extra memory space for temp variable for swapping.

Time Complexities:

• Best Case Complexity: The selection sort algorithm has a best-case time complexity of O(n²) for the already sorted array.
• Average Case Complexity: The average-case time complexity for the selection sort algorithm is O(n²), in which the existing elements are in jumbled ordered, i.e., neither in the ascending order nor in the descending order.
• Worst Case Complexity: The worst-case time complexity is also O(n²), which occurs when we sort the descending order of an array into the ascending order.

In the selection sort algorithm, the time complexity is O(n²) in all three cases. This is because, in each step, we are required to find minimum elements so that it can be placed in the correct position. Once we trace the complete array, we will get our minimum element.