Selection Sort Algorithm
This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.
How Selection Sort Works
- Our original array is [100, 30, 20, 80, 40, 10]
- We divide it into two separate lists within that list. We are not creating new auxiliary lists.
- One sub-list represents sorted numbers and the other represents unsorted numbers.
- We start with the entire list being unsorted.
- We are going to iterate through this unsorted list many times until we find the smallest number.
- Once we find the smallest number, we will append it to the sorted sublist.
- We will keep doing that until we have no elements left in the unsorted sublist and our entire list becomes sorted.
Let’s look at an example step-by-step:
Our unsorted sublist is now reduced by one element and we repeat the search for the smallest number starting from 30. So 30 is our current smallest number stored in the min variable.
We start traversing the unsorted sublist again:
This algorithm has a space complexity of O(1) because all we did was swap numbers within an array in place, and the time complexity is going to be Ο(n^2) because we kept reiterating through parts of the unsorted sublist, we are using two for loops. This is a less performant search algorithm. Selection sort may require a large number of comparisons and it’s not as good as merge sort or quicksort but it’s simple to implement and easy to understand. Let’s implement it in code now.
Selection Sort Implementation in Python
def selection_sort(arr):
for i in range(len(arr)):
#set current element as min
min = i
#check all other elements (to the right of the current element)
for inner in range(i+1, len(arr)):
if arr[inner] < arr[min]:
min = inner
#swap the current element with the min element
arr[i],arr[min] = arr[min],arr[i]
return arr The index variable i denotes the dividing point. Elements to the left of i are sorted, and elements including and to the right of i are unsorted. All elements in the unsorted part are searched to find the index of the element with the smallest value. The variable min stores the index of the smallest element in the unsorted part. Once the element with the smallest value is found, that element is swapped with the element at location i. Then, the index i is advanced one place to the right, and the process repeats. The term “selection” comes from the fact that for each iteration of the outer loop, a value is selected for position i.
Conclusion
The selection sort algorithm works by finding the minimum element of the array and placing it at its correct position. In the selection sort, the first element is selected as the minimum and visits other elements of the array. If any element is found smaller than the current minimum, the minimum value gets updated. This process is repeated for other elements of the array. Complexity Analysis: runtime is O(n²), and space is O(1).
Explore other common sorting algorithms:
