If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the selection sort algorithm in JavaScript and Python.
This article originally published at jarednielsen.com
How to Code the Selection Sort Algorithm
Programming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the problem
Make a plan
Execute the plan
Evaluate the plan
Understand the Problem
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
GIVEN an unsorted array of integers
WHEN we find the lowest unsorted value
THEN we move that value to its proper ordinal position and repeat until all values are in sequence
That’s our general outline. We know our input conditions, an unsorted array, and our output requirements, a sorted array, and our goal is to organize the elements in the array in ascending, or non-descending, order, starting with the smallest elements first.
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
Decomposition
Pattern recognition
Abstraction
Algorithm design
We need something to sort, so let's use this "unsorted" array:
[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
The first step in our process is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?
[10, 1]
We see that we simply need to swap the positions of these two values. Let's pseudocode a solution to this very small problem:
INPUT array
SET first EQUAL TO THE VALUE STORED IN array[0]
SET next EQUAL TO THE VALUE STORED IN array[1]
IF next IS LESS THAN first
SWAP first AND next
So far so good! Let's expand our array and add another value:
[10, 1, 9]
We could hardcode another conditional to check the value stored in the third index, but we're programmers. We immediately recognize a pattern emerging where we will need to select the first value and not only compare it to the second value, but to the third value as well. And then select the second value, and compare it to the third value, all while swapping the location of values when necessary. We need to iterate.
Let's update our pseudocode:
INPUT array
FOR EACH index IN array:
SET first EQUAL TO THE VALUE STORED IN array[0]
SET next EQUAL TO THE VALUE STORED IN array[1]
IF next IS LESS THAN first
SWAP first AND next
Let's step through this...
On the first iteration, we select the first element, 10, and compare it to the next element, 1, which is less than 10, so we swap their positions. Our array now looks like this:
[1, 10, 9]
But! What happens in the next iteration? We again select the first element and compare it to the next element, which is now 9. 9 is greater than 1, so we leave it where it is.
What's the solution?
Abstraction!
We need a means of tracking and updating the index of the "known minimum value".
In this scenario, 1 is our first "known minimum value", but we can see that 9 is less than 10, so after we move 1, the current "known minimum value" to the 0 index, we need to find the next "known minimum value" and compare that to the next value and swap accordingly.
Let's refer to the "known minimum value" as min.
INPUT array
FOR EACH index IN array:
SET min EQUAL TO index
SET next EQUAL TO index + 1
IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]:
SET min EQUAL TO next
SWAP THE VALUE STORED IN array[index] WITH THE VALUE STORED IN array[min]
Let's iterate over our array again:
[10, 1, 9]
On the first iteration, we select 10 because it's the first element, and the value stored inarray[min]. If the value stored in next, in this case 1, is less than the value stored in min, which it is, we reassign min the value of next. So min is now equal to 1. Now we need to swap the value currently stored in array[index], 10, with the value stored in array[min], 1. After the first iteration, our array looks like this:
[1, 10, 9]
On the next iteration, index is equal to 1, so we reassign the value of min with 1. We then reassign the value of next with index + 1, or 2. We compare the value stored in array[next], which is 9, with the value stored in array[min], which is 10. Our conditional evalutes as true, so we reassign the value of min with the value of next and then swap the value stored in array[index] with the value stored in array[min]. Our array now looks like this:
[1, 9, 10]
So far so good. Let's add another value to our array:
[10, 1, 9, 2]
Let's fast forward to the fourth iteration, where our array looks like this:
[1, 9, 10, 2]
What's going to happen here? We're only going to swap the locations of 2 and 10. Our array will look like this:
[1, 9, 2, 10]
What's wrong with our design?
We are only comparing the iterator, index, to the next value.
What's the solution?
Nested iteration. We need to compare every index to all of the following values in the array. Let's update our pseudocode:
INPUT array
FOR EACH index IN array
SET min EQUAL TO index
SET next TO index + 1
FOR EACH next IN array
IF THE VALUE STORED IN array[next] IS LESS THAN THE VALUE STORED IN array[min]
SET min EQUAL TO next
SWAP THE VALUES STORED IN array[index] WITH THE VALUE STORED IN array[min]
Let's step through our pseudocode, using this array:
[10, 1, 9, 2]
On the first iteration of our outer loop, we set min to index, or 0. We then enter our nested loop to iterate over the remaining, or next elements. The next element is equal to index + 1. which in this iteration is 1. Our conditional checks if the value stored in our array at index 1 is less than the value stored in our array at index 0. If this evaluates as true, we set the value of min equal to next. In this iteration, array[next] is equal to 1 and array[index] is equal to 10, so we set min equal to the value stored in next, which is 1. We are still in our nested loop, so we continue comparing the remaining values to min and discover that 1 is the lowest value in our array. We exit our nested loop and swap the value in the 0 index, which is 10, with the vale in the min index, which is 1. Our array now looks like this:
[1, 10, 9, 2]
We are now iterating at the level of our outer loop again, and we select the value in the 1 index, which is now 10. We assign it to min and enter our nested loop. The next value is 9, which is less than 10, so we assign the index of next, which is 2 to min. We continue iterating over the remaining values in our array and find that the next value, 2, is less than 9, so we assign the index of next, which is 3, to min. We exit our nested loop and swap the value stored at array[index] with the value stored in array[next]. Our array now looks like this:
[1, 2, 9, 10]
Looks like a solid plan!
Execute the Plan
Now it's simply a matter of translating our pseudocode into the syntax of our programming language. Let's start with JavaScript...
How to Code the Selection Sort Algorithm in JavaScript
Let's translate our pseudocode to JavaScript:
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
let tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
};
How to Code the Selection Sort Algorithm in Python
Now let's see it in Python...
unsorted = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
def selection_sort(arr):
for i in range(len(arr)):
min = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min]:
min = j
tmp = arr[i]
arr[i] = arr[min]
arr[min] = tmp
return arr
Evaluate the Plan
Can we do better? Do we need to go the end of the array? If our nested loop is comparing the value of the next index to the current index, our outer loop doesn't need to include the last index. We can shave off one operation by setting the condition of our for loop to the length of our array minus 1.
Here it is in JavaScript...
const selectionSort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
let tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
};
Note that we update the second line with the following:
for (let i = 0; i < arr.length - 1; i++) {
Here it is in Python...
def selection_sort(arr):
for i in range(len(arr) - 1):
min = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min]:
min = j
tmp = arr[i]
arr[i] = arr[min]
arr[min] = tmp
return arr
As above, note that we simply update the second line with the following:
for i in range(len(arr) - 1):
Note that we don't - 1 in the condition of the nested loop. If we did, we would never select the final value.
A is for Algorithms
Give yourself an A. Grab your copy of A is for Algorithms
Top comments (0)