Selection Sort in Python

In this guide, we will execute the selection sort algorithm using Python. This algorithm is relatively simple and requires fewer swaps.

In this algorithm, the smallest element from an unsorted array is identified during each iteration and exchanged with the first element of the unsorted portion. This procedure persists until every element is positioned correctly. It is straightforward and operates as an in-place comparison sorting algorithm.

Working of Selection Sort

Below are the procedures that elucidate how the Selection sort algorithm functions in Python.

Consider an unordered array for the implementation of the selection sort algorithm.

[30, 10, 12, 8, 15, 1]

Step - 1: Get the length of the array.

length = len(array) → 6

Step - 2: Initially, we designate the first element as the minimum element.

Step - 3: Next, evaluate the second element against the current minimum. If the second element is less than the first, we designate it as the new minimum.

We then evaluate the second element in relation to the third, and if the third element is lesser than the second, we designate it as the minimum. This procedure continues until we reach the final element.

Step - 4: At the conclusion of each iteration, the smallest element is exchanged with the first position of the unsorted portion of the array.

Step - 5: The process of repeating the second and third steps continues until the array is fully sorted.

Selection Sort Algorithm

The selection sort algorithm as follows.

Algorithm

selection_sort(array)

  repeat (0, length - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

end selection_sort

Selection Sort Program using Python

The code example below demonstrates the implementation of the selection sort algorithm in Python.

Example:

def selection_sort(array):

    length = len(array)

    for i in range(length-1):

        minIndex = i

        for j in range(i+1, length):

            if array[j]<array[minIndex]:

                minIndex = j

        array[i], array[minIndex] = array[minIndex], array[i]

    return array

array = [21,6,9,33,3]

print("The sorted array is: ", selection_sort(array))

Output:

The sorted array is:  [3, 6, 9, 21, 33]

Explanation -

Let's understand the above code -

• ✅ First, we define the selection_sort function that takes array as an argument.
• ✅ In the function, we get the length of the array which used to determine the number of passes to be made comparing values.
• ✅ As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable
• ✅ The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.
• ✅ Find the minimum element in the unsorted list and update the minIndex position.
• ✅ Place the value at the beginning of the array.
• ✅ Once the iteration is completed, the sorted array is returned.
• ✅ At last we create an unsorted array and pass to the selection_sort It prints the sorted array.

Time Complexity of Selection Sort

Time complexity is a crucial factor in determining the duration an algorithm requires to perform sorting. In selection sort, there are two nested loops. The outer loop iterates n times, where n represents the total count of elements.

The inner loop runs for n iterations as well. It assesses the remaining value against the outer loop's value. Consequently, the total number of executions amounts to n*n. Therefore, the time complexity of the merge sort algorithm is O(n²).

Time complexity can be classified into three distinct categories.