Selection Sort Using Python

Selection sort is a type of sorting algorithm which is based on sorting elements in increasing order or ascending order through comparison. This sorting technique does not take extra space except for one memory space which is used for storing the temporary variable. It is a type of in-place sorting that does not require extra memory space and gives the output in the same memory in which the input was stored.

The time complexity of the selection sort is n²,where n is the number of elements. It uses an iterative method to sort the list. Selection sort divides the list into two parts. One is a sorted list that initially contains no elements, and another one contains an unsorted list that, by default, contains all the elements initially.

Working of Selection Sort

1. First, we will set the first element as a minimum.
2. After that, we will compare the minimum value with the second. If the second value is smaller than the minimum value, assign the second element as the minimum value.
3. We will repeat this for all the elements. We will compare all elements with the minimum value, and the smaller one will be assigned as the minimum value.
4. After the first iteration, we will get the minimum value of the list. We will swap the minimum value with the first element.
5. We will set the second element as a minimum and repeat the above steps.
6. After n-1 iterations, where n is the number of elements, we will get a sorted list.

Code for selection sort

def selection_sort( listvalues ):
    n = len( listvalues )
    for i in range( n - 1 ): 
        min_val_index = i


        for j in range( i + 1, n ):
            if listvalues[j] < listvalues[min_val_index] :
                min_val_index = j


        if min_val_index != i :
            temp = listvalues[i]
            listvalues[i] = listvalues[min_val_index]
            listvalues[min_val_index] = temp


    return listvalues




l = [69,11,9,53,2]


print(selection_sort(l))

Output

[2, 9, 11, 53, 69]

Explanation

In the above code, we have used a list l with random elements like 69, 11, 9, 53, and 2. We have used that list as an argument sent to the selection_sort function. Inside the selection_sort function, we have used two for-loops. The first for loop or the outer for loop is used for keeping count of the iterations, and the inner for loop is used for iterating the elements and finding the minimum value. There is a conditional statement too inside the first for loop. The if-statement inside the outer for loop is used for swapping the actual minimum value with the stored minimum value.

Inside the first iteration, the total number of comparisons is n-1. After that, in the second iteration, the total number of comparisons is n-2. In the third iteration, the total number of comparisons is n-3. Similarly, at the n-1th iteration, the number of comparisons will be n-(n-1), which is 1.

Total comparison: (n-1) + (n-2) + (n-3) + ……+ 2 + 1 = n²

Complexity of selection Sort

Best Case : O(n²)

The best case occurs in selection sort when the list is almost sorted. In that case, the number of comparisons is less.

Average Case: O(n²)

The average case occurs in selection sort when mixed order of elements present in the list, increasing and decreasing.

Worst Case: O(n²)

The worst case occurs in selection sort when the list is sorted in opposite order or, in other words, when the list is sorted in decreasing order. In that case, there will be a total n² comparison.

Space Complexity: O(1)

The space complexity of the selection sort is constant or linear because it is an in-place sorting algorithm and does not require extra space for storing the output.

Advantages of Selection Sort

These are some of the following advantages of the selection sort

• It performs very well on lists with less number of elements.
• It is an in-place algorithm which means it does not require a lot of space for sorting. Only one extra space is required, which is used for storing the temporary variable.
• It performs very well when the list is sorted or partially sorted.

Disadvantages of Selection Sort

These are some of the following disadvantages of the selection sort.

• It does not perform well when working on a list with many elements.
• The number of iterations made during the sorting is n², where n is the number of elements in the list.
• Other algorithms have better performance compared to the selection sort.