November 23, 2017

# Selection sort in Python

**Introduction**

Selection sort is a simple in-place (i.e. no auxiliary memory) comparison based sorting algorithm. It is an inefficient algorithm with O(n2) running time as it uses two nested loops.

Here is a summary of steps how the algorithm works:

- Given an unsorted list
- Start with the first element on the left side
- Scan all other elements on the right side and find the smallest
- Swap the smallest element with the first element if they are not equal
- Now the first element is the smallest
- Go to the second element, scan all elements to the right, find the smallest
- Swap the smallest with the second element
- Repeat these steps until all elements are sorted

Here is a cool Gypsy folk dance YouTube video demonstrating selection sort visually:

**Selection sort python code**

Here is an example Python source code:

# Example input list A = [4, 2, 1, 0, -1] # Number of items in the list n = len(A) # Outer loop index (i) goes from (0) to (n-1) for i in range (n-1): # Assume the element at (i) # is the smallest in the list minj = i # Scan all elements to the right of (i) # and find the smallest for j in range(i+1, n): if A[j] < A[minj]: minj = j # Swap the smallest element to the right # of (i) with the element at (i) unless # they are equal if minj != i: x = A[i] A[i] = A[minj] A[minj] = x # Print the sorted array print (A)

Thanks for reading. For questions or feedback, please the comments section below.