As we saw earlier in this chapter, bubble sort is one of the simplest sorting algorithms. Selection sort is an improvement on bubble sort, where we try to minimize the total number of swaps required with the algorithm. It is designed to make one swap for each pass, compared to N-1 passes with the bubble sort algorithm. Instead of bubbling the largest value toward the top in baby steps (as done in bubble sort, resulting in N-1 swaps), we look for the largest value in each pass and move it toward the top. So, after the first pass, the largest value will be at the top. After the second pass, the second largest value will be next to the top value. As the algorithm progresses, the subsequent values will move to their correct place based on their values. The last value will be moved after the (N-1)^th pass. So, selection sort takes N-1 passes to sort N items:

The implementation of selection sort in Python is shown here:

def SelectionSort(list):     
    for fill_slot in range(len(list) - 1, 0, -1):         
        max_index = 0         
        for location in range(1, fill_slot + 1):             
            if list[location] > list[max_index]:                 
                max_index = location         
        list[fill_slot],list[max_index] = list[max_index],list[fill_slot]

When the selection sort algorithm is executed, it will result in the following output:

Note that the final output is the sorted list.