Selection Sort Algorithm

Last Updated on February 2, 2023 by Prepbytes

In this article, we will learn what is selection sort, the selection sort algorithm with an example dry-run, what is selection sort algorithm, and how to write the program for selection sort.

What is Selection Sort?

In the selection sort, the array is sorted by finding the minimum element of the array repetitively. First, find the minimum element from the unsorted part and place that element into the beginning (for ascending order sorting). Continue this process until the array is sorted. Let’s see how the selection sort algorithm works.

The selection sort algorithm works by dividing an array into two subarrays:

• The already sorted subarray
• The remaining unsorted subarray

Now, in each iteration, we will find the minimum element from the unsorted subarray and move this element to the beginning of the unsorted subarray. After the completion of each iteration, the size of the sorted subarray will be increased by 1 and after performing all the iterations the array will be sorted.

Selection Sort Algorithm with an example dry-run:

Lets see how the selection sort algorithm works with a dry-run example. We will take an unsorted array example to understand how the selection sort algorithm works.

We have taken an unsorted array as an example. Now, let’s see how we can sort this array using the selection sort algorithm.

First Pass:
For the first pass, we need to find the minimum element from the index 0 to 4 (0-based indexing). After that, we will replace the minimum element with the first position element.

In the above image, we can see that the minimum element from index 0 to 4 is 10. So we will replace 10 with 60.

Now, we can see that the first half till 10 is sorted, and the remaining is unsorted.

Second Pass:
For the first pass, we need to find the minimum element from the index 1 to 4. After that, we will replace the minimum element with the second position element.

In the above image, we can see that the minimum element from index 1 to 4 is 20. So we will replace 20 with 40.

Now, we can see that the first half till 20 is sorted, and the remaining is unsorted.

Third Pass:
For the first pass, we need to find the minimum element from the index 2 to 4. After that, we will replace the minimum element with the third position element.

In the above image, we can see that the minimum element from index 2 to 4 is 30. So we will replace 30 with 40.

Now, we can see that the array is already sorted. Still, we will perform the remaining passes.

Fourth Pass:
For the first pass, we need to find the minimum element from the index 3 to 4. After that, we will replace the minimum element with the fourth position element.

In the above image, we can see that the minimum element from index 3 to 4 is 40, and 40 is at its right position so we will not swap anything.

Fifth Pass:
For the first pass, we need to find the minimum element from index 4. After that, we will replace the minimum element with the fifth position element.

In the above image, we can see that the minimum element at index 4 is 60, and 60 is at its right position so we will not swap anything.

Selection Sort Algorithm:

• selection_sort(arr,n)
  • run loop from 0 to n-1
    • initialize the first unsorted element as the minimum
    • run loop to iterate through the unsorted array
      • if the current element < minimum
      • set the new minimum as the current element
    • swap the minimum with the first unsorted position
• end selection sort

Selection Sort Program:

Lets see how to write the program for selection sort.

# Python program to perform selection sort

def selection_sort(arr,n):
    for i in range(n):
        
        # Find the minimum element in remaining
        # unsorted array
        min_index = i
        for j in range(i+1, n):
            if arr[min_index] > arr[j]:
                min_index = j
                
        # Swap the found minimum element with
        # the first element	
        arr[i], arr[min_index] = arr[min_index], arr[i]


arr = [60, 40, 20, 30, 10]
n=len(arr)

print("Array befor performing the selection sort: ")
for i in range(n):
    print(arr[i],end=" ")
print()
selection_sort(arr,n)
print ("Array after performing the selection sort: ")
for i in range(n):
    print(arr[i],end=" ")

Output:

Array before performing the selection sort: 
60 40 20 30 10 
Array after performing the selection sort: 
10 20 30 40 60 

Time Complexity: O(n^2) we are using the outer loop to traverse through an array and we are also using an inner loop to find minimum. Both loops runs n times. Thus, the time complexity is O(n*n) = O(n^2).

Space Complexity: O(1) we are not using any extra space to perform the selection sort algorithm. We are performing only swaps and the most we can perform total n swaps and performing swaps takes constant space.

FAQs Related to Selection Sort Algorithm

1) The Selection sort algorithm is in place?
Yes, the selection sort algorithm is in place. The selection sort algorithms do not require any extra space.

2) The selection sort algorithm is stable?
This selection sort algorithm is not stable. Though, we can achieve stability in the selection sort using a similar method to the insertion sort.

3) How many maximum steps require in the selection sort algorithm?
In the worst case of the selection sort algorithm, we might perform maximum n (size of an array) swaps.