EXAMPLE CODE LISTING We didn’t show you the code to sort the music list, but following is
some code that will do something very similar: sort an array from
smallest to largest. Let’s write a function to find the smallest element
in an array:
def findSmallest(arr):
smallest = arr[0]
Stores the smallest value smallest_index = 0
Stores the index of the smallest value for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
Now you can use this function to write selection sort:
def selectionSort(arr):
Sorts an array newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
Selection sort Checking fewer elements each time Maybe you’re wondering: as you go through the operations, the number
of elements you have to check keeps decreasing. Eventually, you’re down
to having to check just one element. So how can the run time still be
O(
n 2
)? That’s a good question, and the answer has to do with constants
in Big O notation. I’ll get into this more in chapter 4, but here’s the gist.
You’re right that you don’t have to check a list of
n elements each time.
You check
n elements, then
n – 1,
n - 2 … 2, 1. On average, you check a
list that has
1
/
2
×
n elements. The runtime is O(
n ×
1
/
2
×
n ). But constants
like
1
/
2
are ignored in Big O notation (again, see chapter 4 for the full
discussion), so you just write O(
n ×
n ) or O(
n 2
).
