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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# 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.
About Author
Mohammed Abualrob
Software Engineer @ Cisco