Selection Sort in Python

Selection sort is a sorting algorithm with time complexity of O(n²). This is an in-place sorting algorithm in data structures and an algorithm used rarely due to its high time complexity. The algorithm sorts the elements in the array from left to right beginning from the 0th element.

Let us now see how the algorithm works before implementing it. To do this we divide the elements into two parts, the sorted and the unsorted part.
1. We select the left-most element in the unsorted part.
2. Moving to the right, we check if any other element is less than the selected element.
3. If a lower value element exists, that element is selected as the least element and this process goes on until the end index.
4. If no other element is less than the selected element, we go back to step 1 and repeat the iteration from the (n+1)th element.
5. After getting the least value, we add the element into the sorted part of the list and do not consider it for the next iteration i.e. after n elements are sorted we start with step 1 again from (n+1)th element.

The below python code shows the python implementation of the selection sort algorithm.

import random
def selection_sort(arr):
  size = len(arr)
  for i in range(size - 1):
    min_index = i
    for j in range(min_index + 1, size):
      if arr[j] < arr[min_index]:
        min_index = j
    if i != min_index:
      arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr
ls = []
for _ in range(500):
  ls.append(random.randint(0, 500))
print(selection_sort(ls))