LetMyPeopleCode.com

A blog about software, schmaltz, and monkey-patches for the soul

Menu
  • About Greg
  • About LMPC
  • Privacy Policy
Menu
"The Coding Interview"

The Coding Interview: Implement a Bubble Sort

Posted on January 27, 2022January 26, 2022 by Greg Bulmash

This series answers coding interview questions from the Coding Interview Prep collection at freeCodeCamp. You can find more with the interview questions tag.

I’ve had 8 different blogs since 1995, two of which still exist, though only one gets updated at all. Back in July of 2019, on the blog I most recently took offline, I did a couple of blog posts on some basic sort algorithms (bubble and selection). My Bubble Sort post is still available on the Wayback Machine.

In nearly 30 months, I’ve completely forgotten how to even explain a bubble sort, much less implement it, because if you don’t reinforce something repeatedly, the memory of it degrades. I remembered I did the blog post, but that’s it.

All I’ve copied is the explanation of how the sort works: “Basically, a bubble sort function walks through an array, comparing each value to its right-hand neighbor and swapping them if the neighbor is smaller.”

This will walk through the array until it makes a complete pass without having to do a swap. Because of the number of operations for most sorts, it’s one of the least efficient sorts.

Solution Explained

First I set a swaps variable to 1 to make sure the outer loop ran at least once. Internally, the loop sets swaps to 0, so when it encounters a sorted array, it won’t run again.

Then an internal loop that will loop from index 0 to the second-to-last index of the array. Since the comparison compares ahead, there’s no sense in going to the last element since there’s nothing to compare it to.

If arr[i] is greater than arr[i+1], swap them. For that, I create a temporary variable to hold the current index value so it’s not clobbered when I move the value of index i+1 into index i. If a swap occurs, it increments swaps, which will require another iteration of the outer loop. When no swaps occur, the outer loop terminates and the function returns the sorted array.

Solution note

It’s worth looking at my 2019 bubble sort in the fewest lines solution, because it’s 13 lines vs the 15 here.

In that, I eliminated one line by using a do... while loop, instead of a while loop, which ensures at least one run of the outer loop and removes the need to initialize or set a value for swaps outside of the loop.

I eliminated another line by using Array.prototype.forEach() to walk the array, because it will provide both the index and the value of that index as arguments to the callback function, removing the need for a line declaring curr as a temporary value holder.

Is the 2019 version any faster? Dunno. Testing that feels like testing whether adding a rear spoiler will improve the 0-60 time of a minivan. Maybe, but does it matter?

I believe the 15 line version might be a little more readable to a beginner.

Solution

function bubbleSort(array) {
  let swaps = 1;
  while (swaps > 0){
    swaps = 0;
    for(let i = 0; i < array.length - 1; i++){
      if(array[i]>array[i+1]){
        let curr = array[i];
        array[i] = array[i+1];
        array[i+1] = curr;
        swaps++;
      }
    }
  }
  return array;
}

 

Related

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Recent Posts

  • My first commute into Seattle since COVID
  • Lenovo P12 Review: A Second Screen – With Caveats
  • Defective Quidel QuickVue COVID Tests
  • The Great American Browser Hunt
  • Chrome’s Usability Crime

Archives

  • April 2022
  • March 2022
  • February 2022
  • January 2022
  • November 2021
  • May 2021
  • April 2020
  • March 2020

Categories

  • Apps
  • Games
  • Hardware
  • JavaScript
  • Mobile
  • Productivity
  • Programming
  • Society & Culture
  • Teaching Code
  • Tech Career
  • Uncategorized
  • WebTech
  • Writing

Tag Cloud

browser hunt code sample commute CX game demo hardware review health interview questions j job hunt diary Mac meta-coding OneNote review Windows

©2022 LetMyPeopleCode.com | Theme by SuperbThemes