Objectives

By the end of this chapter you should be able to:

• Define and implement simpler sorting algorithms like bubble, insertion, and selection sort
• Understand the runtimes and limitations of bubble, insertion, and selection sort

Introduction

Sorting is an important feature to have in any programming language. Whether you want to sort an array of numbers in JavaScript, or a list of strings in Python, it's very common to have a set of data that you want to order in some way.

There are a number of well-known algorithms used to sort data. However, not all of these algorithms are created equal: some are significantly more efficient than others. In this chapter, we'll look at three algorithms that are comparatively more straightforward, even though they aren't the most efficient.

Bubble Sort

One of the simplest algorithms for sorting an array of elements is bubble sort. The algorithm goes as follows

• For each element in the array, compare it with the next element (the element to the right).
• If the element is greater than the value on the right, swap the two values.
• Continue to swap until you have reached the end of the array. At this point the rightmost element will be in its correct place.
• Start at the beginning of the array and repeat this process. Since the rightmost element from the last iteration is now sorted, this process will terminate earlier and earlier each time you repeat.

Here is a nice GIF of the algorithm in action; you can also see an excellent visualization here

And here is a great video describing it in more detail.

So how does the algorithm perform in terms of its time complexity? Unfortunately, the algorithm is typically O(n²) because there's a nesting of loops: you run through the array, and at each iteration you have to run through a subarray of the original array. In the best case scenario, bubble sort will run at O(n) since only one complete iteration will be necessary.

Insertion Sort

Another simple algorithm for sorting an array of elements is insertion sort. The algorithm goes as follows:

• Start by picking the second element in the array (we will assume the first element is the start of the "sorted" portion)
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion to place the element in the correct place.
• Repeat until the array is sorted.

Here is a nice GIF of the algorithm in action; you can also see an excellent visualization here

And here is a great video describing it in more detail.

Like bubble sort, insertion sort typically is O(n²), since you need to go through the array for each element in it in order to find its proper position. In the best case scenario, insertion sort will run at O(n) since only one complete iteration will be necessary.

Selection Sort

Another simple algorithm for sorting an array of elements is selection sort. The algorithm goes as follows:

• Assign the first element to be the smallest value (this is called the minimum). It does not matter right now if this actually the smallest value in the array.
• Compare this item to the next item in the array until you find a smaller number.
• If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.
• If the "minimum" is not the value (index) you initially began with, swap the two values. You will now see that the beginning of the array is in the correct order (similar to how after the first iteration of bubble sort, we know the rightmost element is in its correct place).
• Repeat this with the next element until the array is sorted.

Here is a nice GIF of the algorithm in action; you can also see an excellent visualization here

And here is a great video describing it in more detail.

Just like bubble sort and insertion sort, selection sort is O(n²). In fact, it's O(n²) even in the best case; try to convince yourself why this is true.

Exercises

Once you feel like you have a solid grasp of these algorithms conceptually, it's time to try implementing them in JavaScript. Complete Part I of the exercises here.