Sorting Algorithms

Examples

1. Sorting numbers from smallest to largest
2. Sorting names alphabetically
3. Sorting movies based on release year

Why do we need to learn this?

. Sorting is an incredibly common taks, so it's good to know how it works . there are many different ways to sort things, and different techniques have their own advantages and disadvantages

JavaScript Built in sort method

...but it doesn't always work the way you expect

example:

["Steele", "Colt", "Data Structure", "Algorithms"].sort() =>

["Algorithms", "Colt", "Data Structures", "Steele"]

that make sense, that sorted alphabetically.

another example:

[6, 4, 15, 10].sort() => [10, 15, 4, 6] => that does not make sense.

Telling JavaScript how to sort

. The built-in sort method accepts an optional comparator funtion . You can use this comparator function to tell JavaScript how you want it to sort . The comparator looks at pairs of elements (a and b), determines their order on the return value . If it returns a negative number, a should come before b . If it returns positive number, it should come after b . If it returns 0, a and b are the same as far as the sort is concerned

example:

function numberCompare(num1, num2) {
  return num1 - num2;
}

[6, 4, 15, 10].sort(numberCompare); // [4, 6, 10, 15]

Bubble Sort

bubble sort is not all that efficient, it's not that commonly used, it's only have one use case.

A sorting algorithm where the largest values bubble up to the top!

how it works: we have this array => [29, 10, 14, 30, 37, 14, 18]

as we loop through each item, we compare it to the next item, and if this one is larger than the next value, and if it is => we swap the values => so swaping is the important thing to the bubble sort

Before we sort, we must swap!

Many sorting algorithms involve some type of swapping functionality (e.g. swapping to numbers to put them in order)

function swap(arr, idx1, idx2) {
  return [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
}

BubbleSort Pseudocode

. Start looping from with a variable called i the end of the array towards the beginning

. Start an inner loop with a variable called j from the beginning until i - 1

. Return the sorted array

. If arr[j] is greater than arr[j + 1], swap those two values!

naive solution

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[j] > arr[j + 1]) {
        // swap
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }

  return arr;
}

bubbleSort([37, 45, 29, 8])