DEV Community

Cover image for Sorting Algorithms with Javascript (Part 1)
Kelvin Wangonya
Kelvin Wangonya

Posted on • Updated on

Sorting Algorithms with Javascript (Part 1)

I've been learning a lot about data structures and algorithms lately and I've noticed in my reading that there aren't a lot of examples showing implementations of algorithms in Javascript. You'll mostly find examples in Java, Python, C, C++ etc. Maybe there's a reason for preferring these languages over Javascript? I'm not sure.

In this first part, I'm going to show Javascript implementations of three sorting algorithms:

  • Merge sort
  • Insertion sort
  • Bubble sort

This is not intended to be an in-depth explanation on the ins and outs of how the algorithms work and their performance. If you'd rather read about that, here's a nice resource I found: Sorting Algorithms

To keep things simple, I'll be sorting a simple list list having only 5 elements [4, 2, 3, 1, 5].

Merge Sort

Merge sort uses a divide-and-conquer approach to sort elements in an array. Basically, what this means is that instead of dealing with the array as a whole, it continually splits it in half until both halves are sorted, then the halves are merged into one solved list.

Visual

merge-sort

Code

function mergeSort(list) {
  const len = list.length
  // an array of length == 1 is technically a sorted list
  if (len == 1) {
    return list
  }

  // get mid item
  const middleIndex = Math.ceil(len / 2)

  // split current list into two: left and right list
  let leftList = list.slice(0, middleIndex)
  let rightList = list.slice(middleIndex, len)

  leftList = mergeSort(leftList)
  rightList = mergeSort(rightList)

  return merge(leftList, rightList)
}

// Solve the sub-problems and merge them together
function merge(leftList, rightList) {
  const sorted = []
  while (leftList.length > 0 && rightList.length > 0) {
    const leftItem = leftList[0]
    const rightItem = rightList[0]
    if (leftItem > rightItem) {
      sorted.push(rightItem)
      rightList.shift()
    } else {
      sorted.push(leftItem);
      leftList.shift()
    }
  }

  // if left list has items, add what is left to the results
  while (leftList.length !== 0) {
    sorted.push(leftList[0])
    leftList.shift()
  }

  // if right list has items, add what is left to the results
  while (rightList.length !== 0) {
    sorted.push(rightList[0])
    rightList.shift()
  }

  // merge the left and right list
  return sorted
}

const list = [4, 2, 3, 1, 5]

const sorted = mergeSort(list)

console.log(sorted)
Enter fullscreen mode Exit fullscreen mode

Insertion Sort

Insertion sort builds the final sorted list one element at a time. It does this by taking one element, comparing it to the rest of elements in the list, finding its right position, and then placing it there.

This is known as comparison-based sorting.

Visual

insertion-sort

Code

function insertionSort(list) {
  const len = list.length
  for (let i = 1; i < len; i++) 
  {
    if (list[i] < list[0]) 
    {
      // move current element to the first position
      list.unshift(list.splice(i,1)[0])
    } 
    else if (list[i] > list[i-1]) 
    {
      // maintain element position
      continue
    } 
    else {
      // find where element should go
      for (let j = 1; j < i; j++) {
        if (list[i] >= list[j-1] && list[i] <= list[j]) 
        {
          // move element
          list.splice(j, 0, list.splice(i,1)[0])
        }
      }
    }
  }
  return list
}

const list = [4, 2, 3, 1, 5]

const sorted = insertionSort(list)

console.log(sorted)
Enter fullscreen mode Exit fullscreen mode

Bubble Sort

Another example of a comparison-based sorting algorithm, Bubble sort compares each pair of elements in a list and swaps them if they are out of order until the list is sorted.

Visual

bubble-sort

Code

function bubbleSort(list)
{
    let swapped
    let n = list.length-1
    do {
        swapped = false
        for (let i=0; i < n; i++)
        {
            // compare pairs of elements
            // if left element > right element, swap
            if (list[i] > list[i+1])
            {
               const temp = list[i]
               list[i] = list[i+1]
               list[i+1] = temp
               swapped = true
            }
        }
    } 
  // continue swapping until sorted
  while (swapped) 

  return list
}

const list = [4, 2, 3, 1, 5]

const sorted = bubbleSort(list)

console.log(sorted)
Enter fullscreen mode Exit fullscreen mode

Thats it! 😊 And, incase you're wondering, I used this site to make the visuals.

In the next part, I'll be going through:

  • Quick sort
  • Heap sort
  • Counting sort

Top comments (10)

Collapse
 
quintanilha6 profile image
João Quintanilha • Edited

Hello there! First let me thank you for the article, it helped me a lot. As I was developing an insertion sort I came across your code and used it, although you have a litle mistake I ended up finding.

instead of:
if (list[i] > list[j-1] && list[i] < list[j])

you should have (= is missing on second validation):
if (list[i] > list[j-1] && list[i] =< list[j])

Otherwise, it wont sort. Once again, thank you!

Collapse
 
wangonya profile image
Kelvin Wangonya

Hey there! I'm glad you found it helpful. Thanks for that 😄.

The code seems to work just fine with the test list provided though. Would you mind explaining why the = is necessary? Or maybe share the list you tested the code with so I can also try it.

Ps: The = should be on the other side of the < in your example though, like so: if (list[i] > list[j-1] && list[i] <= list[j]) 🙂

Collapse
 
theafricantechie profile image
Lynn Mugambi

Hey Kinyanjui, thanks again for the post! Super helpful!

Just hoping on to this, I noticed an issue with the same line of code where if a list has two elements with the same value it won't sort it properly. i.e. [4, 2, 3, 2, 1, 5] gives [ 1, 2, 3, 4, 2, 5 ] as a result.

Adding an = sign to the first argument makes all the difference! if (list[i] >= list[j-1] && list[i] < list[j]). It now returns [ 1, 2, 2, 3, 4, 5 ] :)

Thread Thread
 
wangonya profile image
Kelvin Wangonya

Thanks Lynn. I've edited the code to include your fix.

Collapse
 
gragoon profile image
Adrian Vaucoret

Hello guy ! Nice post !

What is the faster sort algorithm ? Is it depends of number of elements ?

Collapse
 
wangonya profile image
Kelvin Wangonya

Thanks for reading!

In this case, Merge sort is the faster of the three with time complexity O(nlogn). Time complexity (the estimated time taken by running an algorithm) is measured by how many operations are executed so yes, the number of elements will matter, but not as much as the order of the elements:

  • Worst-case time complexity (input elements in reversed order)
  • Best-case time complexity (already sorted)
  • Average-case time complexity (elements in random order)
Collapse
 
adityasridhar profile image
Aditya Sridhar

Nice Article. Thanks for taking the time to write this :)

Collapse
 
wangonya profile image
Kelvin Wangonya

Thanks for taking the time to read Aditya :)

Collapse
 
donut87 profile image
Christian Baer

Hey, nice overview. One thing though. Merge sort is also comparison based. To sort in the end, you always compare two elements.

Collapse
 
wangonya profile image
Kelvin Wangonya

Nice catch! Thanks