Selection Sort algorithm is an in-place comparison-based algorithm. The algorithm divides the array into two segments:
The algorithm involves finding the minimum or maximum element in the unsorted portion of the array and then placing it in the correct position of the array.
Now that we know how the algorithm works in theory, let’s see how to write the code to implement it.
def selectionSort(array):n = len(array)for i in range(n):# Initially, assume the first element of the unsorted part as the minimum.minimum = ifor j in range(i+1, n):if (array[j] < array[minimum]):# Update position of minimum element if a smaller element is found.minimum = j# Swap the minimum element with the first element of the unsorted part.temp = array[i]array[i] = array[minimum]array[minimum] = tempreturn array# Driver codearray = [13, 4, 9, 5, 3, 16, 12]print(selectionSort(array))
The code above shows how to write Selection Sort in Python. Now let’s understand it in detail.
The first for
loop traverses the whole of the array. It initially sets the minimum
to be the index of the first element in the unsorted array.
The inner for
loop traverses the remaining portion of the array to find the position of the minimum value in this portion. Once complete, it swaps the minimum value in the unsorted portion with the first value of the unsorted portion.
It repeats the procedure by moving to the next value in the list and considering it to be the new minimum.