LetMyPeopleCode.com

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

Menu
  • About Greg Bulmash
  • Greg Talks Tech
  • 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

  • Job Hunt Diary 2023: Verizon Is Passive-Aggressive?
  • Job Hunt Diary 2023: Eliciting Responses
  • Job Hunt Diary 2023: And so on, and so on…
  • Job Hunt Diary 2023: Freelancing and warning words
  • Job Hunt Diary 2023: Not all job fairs are created equal

Archives

  • March 2023
  • February 2023
  • January 2023
  • December 2022
  • November 2022
  • September 2022
  • May 2022
  • April 2022
  • March 2022
  • February 2022
  • January 2022
  • November 2021
  • May 2021
  • April 2020
  • March 2020

Categories

  • Apps
  • Computing
  • Frameworks and Libraries
  • Games
  • Hacks
  • Hardware
  • JavaScript
  • Mac
  • Mobile
  • Other Art Projects
  • Productivity
  • Programming
  • Projects
  • Python
  • Society & Culture
  • Teaching Code
  • Tech Career
  • Uncategorized
  • WebTech
  • Writing

Tag Cloud

Adobe advertising bad ads browser hunt clown car code sample comcast commute copy writing CX design Developer Relations dev rel evernote game demo google drive hardware review health home office home studio internet interview questions j job hunt job hunt diary Mac magento meta-coding OneNote PEO productivity review speedtest t-mobile Windows xfinity

©2023 LetMyPeopleCode.com | Theme by SuperbThemes