lesson-notes

Sorting Algorithms Part 1

Learning Objectives

• Explain why there are so many sorting algorithms
• Review breaking the problem down into smaller parts
• Sort an array of numbers using bubble sort

There are Many Sorting Algorithms

Sorting is often an essential part of a good number of applications. For example, on a website, you might want to sort a list of shoes by price. If you are working on the front end, you usually have a limited number of items to sort on a page (less than 100), so developers would rely on the built-in .sort() function, which is an implementation of a sorting algorithm.

Which algorithm does JavaScript use? It's complicated, and it can depend on which browser one is using. The engineers who build JavaScript in the browser are the ones who take the time and effort to choose the best algorithm for general use.

A large part of determining the most suitable algorithm goes back to the concepts of Big O and choosing the right one in terms of time and space efficiency. Other factors are also considered, like how likely is what is being sorted already somewhat sorted or very random. Here is a visualization of the performance of a few sorting algorithms and different types of sorted data sets

Today we'll look at one of the simpler sorting algorithms: Bubble sort.

Simplifying the Problem

For the pre-lesson, you were asked to sort an array of numbers. You were given a lot of extra code to sort through, think about/try to ignore. This typically makes solving a problem much harder.

When working on a project with many other code/features/complications, getting lost in the code is easy. Implementing a new feature can feel overwhelming and complicated.

You always have a choice of creating a little coding sandbox. You can do this with plain JS/HTML/CSS files on your computer, codepen, or create-react-app to quickly start a new project.

You can also create a git repo and then make multiple branches to try different solutions without worrying you will lose progress as you try new ideas.

Let's create our own sandbox by creating a new random array representing a possible output from our Deck Of Cards.

const cards = [10, 3, 10, 8, 10, 11, 7, 10, 9, 6, 5, 2, 4];

Bubble Sort

Bubble sort compares two elements that are next to each other,

• If they are in the correct order, it moves along to the next pair
• If they are in the wrong order, they are swapped, and then it moves along to the next pair
• It repeats this process over and over again until no swaps have been made until it has completed its sorting

Let's code it:

const bubbleSort = (arr) => {
 for let (i = 0; i < arr.length; i++) {
 // iterate over the array
 }
}

const bubbleSort = (arr) => {
 for (let i = 0; i < arr.length; i++) {
 // compare if the first item is larger than the one next to it. If yes, then swap the positions
 if (arr[i] > arr[i + 1]) {
 [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
 }
 }
 return arr
}

console.log(bubbleSort(cards))

The above takes us through one iteration,

[3, 10, 8, 10, 10, 7, 10, 9, 6, 5, 2, 4, 11];

But we must keep iterating until the algorithm makes it through the loop without swapping.

const bubbleSort = (arr) => {
  do {
    swapped = false;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);

  return arr;
};

console.log(bubbleSort(cards));

Thought question: Why are we using a do while loop instead of a while loop?

Determine Big O on your own, then check:

Big O

Runtime: O(n^2)

Memory O(1)

Further Reading

Go back to the resources in the pre-lesson and review them.

Google bubble sort JavaScript and read a few explanations and versions. You'll notice slight differences in the approaches, whether the syntax or choosing a for loop instead of a while loop. Take your time reviewing so you can be sure you can implement bubble sort using your pseudo-code without having to look up a possible solution.

Go back to your own attempt at sorting the cards. Was it similar to bubble sort? If it was different, take time to compare and contrast your approach.