Complete Python Selection Sort Algorithm | Code Complexity

As we know, sorting is a technique to arrange the elements in the array either in ascending or descending order. And there are multiple sorting algorithms such as bubble sort, insertion sort, quick sort, selections sort…

Here we will see Python selection sort.

Before writing the code…

What is Selection Sort Algorithm?

Here is pseudo-algorithm for selection sorting.

• Take the array (containing elements to sort) as an input
• Iterate through all the elements in the array (says element as i)
• Find the smallest elements from rest of the array (array elements next to i’s)
• Swap the smallest element with i

If you understand the pseudo-algorithm, I would like if you minimize the browser and try to write code yourself.

Python Selection Sort Program

#swap two elements in nArr at postion i and j
def swap(i, j, nArr):
    if i!=j:     
        temp = nArr[j]
        nArr[j] = nArr[i]
        nArr[i] = temp

#function to sort elements in the list
def selectionSort(nArr):    
    for i in range(0, len(nArr)):
        small = i
        for j in range(i+1, len(nArr)):
            if nArr[j] < nArr[small]:
                small = j
        swap(i, small, nArr)

#list containing elements to sort        
nArr = [34,456, 5, 5,67]
selectionSort(nArr)
print(nArr)

Here in the above program, I have a hardcoded list. You can even take the list elements as user input.

Output:

[5, 5, 34, 67, 456]

In the first pass, the first element in the array will be in sorted position. After the second pass, two elements in the array will be sorted.

Likewise…

If you have n elements, after n-1 pass, n-1 elements will be sorted. If you arrange first n-1 elements in the array in the right position, the last element automatically will be in the right position.

So in each pass, you need to swap the elements at most one time. So in selection sort, you need a maximum n-1 pass and so the swaps to sort all the elements in the array.

If you compare with the bubble sort, in every pass we swap the elements multiple times. So you can consider the selection sort as improvement in bubble sort.

Above code, sort the elements in ascending order. If you want the same program to sort elements in descending order, replace < with > inside the function selectioSort().

For sorting, you need to take Numeric data types values. Just to give little tweak, you can also use a list containing characters to sort.

Time complexity of Selection Sort

As you have to compare each element with other elements from an array list, it has a time complexity of o(n^2) in all three cases (best, average and worst case).

As it takes O(n^2) time, it is not considered as an efficient algorithm for sorting if you have minimal time.

Memory Complexity of Selection Sort

Selection sort does not require any extra memory (except for swapping). So, it takes constant time O(1), despite the number of elements in the array.

You need to swap the elements, only if it is required. If your array is already sorted, there will be zero numbers of swapping.

Just to clarify…

Here we are using the list to sort. As tuple is an immutable data structure in Python, you can not use tuple for sorting. For more, you can read List vs Tuple in Python.

If you understand the logic behind Python selection sort, it is easy to implement in any programming language. Any doubt? Write in the comment section.