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!

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

function bubbleSortAscend(arr) {
    for (let i = arr.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            if (arr[j+1] < arr[j]) {
                swap(arr, j, j+1);
            }
        }
    }

    return arr;
}

function bubbleSortDescend(arr) {
    for (let i = arr.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            if (arr[j+1] > arr[j]) {
                swap(arr, j, j+1);
            }
        }
    }

    return arr;
}

console.log(bubbleSortAscend([9, 3, 6, 24, 17]));
console.log(bubbleSortDescend([9, 3, 6, 24, 17]));

BubbleSort Optimization

check do we need more swaps???

function bubbleSort(arr) {
    let noSwaps;
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            if (arr[j+1] > arr[j]) {
                swap(arr, j, j+1);
                noSwaps = false;
            }
        }
        if (noSwaps) break;
    }

    return arr;
}

Big O of BubbleSort

in general it is O(n^2), however if the data is nearly sorted or already sorted, then with optimized version noSwaps it's more like linear time. O(n) => that is the best case. So if we know that our data is nearly sorted, so we can use BubbleSort

Selection Sort

Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position.

for example we have this array: [5, 3, 4, 1, 2] => what we're gonna do is that we're start from at the beginning and find the minimum value and put it at first of the array. in bubble sort we're finding largest value, but in selection sort we're finding the smallest value.

We are going through and selecting the smallest element (the minimum) and then put it at the beginning in this as well we use swapping method.

Selection Sort Pseudocode

. Store the first element as the smallest value you've seen so far.

. Compare this item to the next item in the array until you find the smaller value.

. Repeat this with the next element until the array is sorted

What do we actually saving, we're not actually saving the value itself, what we're gonna save is the index of the value that we found, so that we can swap