Skip to main content

Sorting & Searching

In Js programming, an Algorithm is a clear set of steps that tells the computer how to solve a problem. Think of it as giving the computer specific instructions to complete a task. For example, imagine you want the computer to add up a list of numbers. You could write an algorithm to go through each number, one by one, and add them together until it reaches the end of the list.

Here’s a simple algorithm example in JavaScript:

let numbers = [2, 4, 6, 8]; // List of numbers
let total = 0; // Start with total as 0

for (let i = 0; i < numbers.length; i++) {
  // Go through each number
  total += numbers[i]; // Add each number to total
}

console.log(total); // Print the total sum

This algorithm is exactly like a Recipe for cooking, it’s a series of steps that the computer follows to calculate the sum of all the numbers in the list. Algorithms help break down tasks so the computer can solve them easily and quickly!

Let's deep dive into the most common algorithm in sorting, searching and recursive process.

Sorting​

Bubble Sort​

magine you have a row of numbered cards that need to be sorted from smallest to biggest. Here’s how Bubble Sort works:

  1. Compare Two Cards: Start with the first two cards. If the left card is bigger than the right card, swap them.

  2. Move Along the Line: Go to the next pair and repeat. Keep moving right until you reach the end.

  3. Repeat: Go back to the start and repeat until no swaps are needed. The biggest number will "bubble up" to the end each round.

Here's the function to solve this problem:

Code
const bubbleSort = (numberArr) => {
  // Make copy of the original array
  // Whatever the change to the copy won't modify the original
  const numbers = [...numberArr];
  for (let i = 0; i < numbers.length; i++) {
    for (let j = 0; j < numbers.length - i - 1; j++) {
      if (numbers[j] > numbers[j + 1]) {
        [numbers[j], numbers[j + 1]] = [numbers[j + 1], numbers[j]];
      }
    }
  }

  return numbers;
};

export default { bubbleSort };

Then a test we can test it:

Test Cases
import { bubbleSort } from "code.js";

QUnit.module("Bubble Sort", () => {
  QUnit.test.each(
    "should bubble short",
    [
      [
        [5, 3, 8, 4, 2],
        [2, 3, 4, 5, 8],
      ],
    ],
    (assert, [a, expected]) => {
      assert.deepEqual(
        bubbleSort(a),
        expected,
        `Bubble sort: ${JSON.stringify(a)} => ${JSON.stringify(expected)}`
      );
    }
  );
});
Code In Action

Click the Test Box on the right 👉, then copy the above Code and Test Cases and paste into the same section in Test Box to see the Test in action.

Quick Sort​

magine you’re sorting cards, like arranging a messy pile into neat order. Here’s how we’ll use Quick Sort:

  1. Pick a Special Card: Choose one card in the pile. This is the “pivot” card, which helps us split the cards.

  2. Make Two Piles: Put all smaller cards in one pile and larger ones in another.

  3. Repeat Until Sorted: For each pile, pick a new “pivot” and split again until you end up with single-card piles.

  4. Put Together: Stack them back up, all sorted!

In code, it would look something like this:

Code
const quickSort = (arr, asc = true) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length - 1; i++) {
    if ((asc && arr[i] < pivot) || (!asc && arr[i] > pivot)) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left, asc), pivot, ...quickSort(right, asc)];
};

export { quickSort };
Test Codes
import { quickSort } from "code.js";

QUnit.module("Sort", () => {
  QUnit.test.each(
    "should quicker sort asc",
    [
      [
        [11, 10, 9, 8, 6, 7, 4, 2, 1, 3, 5],
        true,
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
      ],
      [
        [11, 10, 9, 8, 6, 7, 4, 2, 1, 3, 5],
        false,
        [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1],
      ],
    ],
    (assert, [number, isAcs, expected]) => {
      assert.deepEqual(
        quickSort(number, isAcs),
        expected,
        `test: ${number.join(", ")} => ${expected.join(", ")}`
      );
    }
  );
});
Code In Action

Click the Test Box on the right 👉, then copy the above Code and Test Cases and paste into the same section in Test Box to see the Test in action.

Searching​

Binary Search is great when you already have sorted cards, and you want to find a specific one.

  1. Divide and Check: Start in the middle. If the middle card is what you’re looking for, you’re done!

  2. Narrow Down: If it’s smaller, look in the left half; if it’s bigger, look in the right half.

  3. Repeat: Keep dividing and checking the middle of each half until you find the card or run out of options.

Try this code:

Code
const binarySearch = (haystack, needle) => {
  let l = 0,
    h = haystack.length,
    m;
  do {
    m = Math.floor((l + h) / 2);

    if (haystack[m] === needle) {
      return true;
    }
    if (needle < haystack[m]) {
      h = m;
    } else {
      l = m + 1;
    }
  } while (l < h);

  return false;
};

export { binarySearch };

The test:

Test Codes
import { binarySearch } from "code.js";

QUnit.module("Binary search", () => {
  QUnit.test.each(
    "should double linked list",
    [
      [[1, 2, 3], 2, true],
      [[1, 2, 3, 7, 9, 10, 24], 24, true],
      [[1, 2, 3, 7, 9, 10, 24], 1, true],
      [[1, 2, 3, 7, 9, 10, 24], 9, true],
      [[1, 2, 3, 7, 9, 10, 24], 8, false],
    ],
    (assert, [arr, n, expected]) => {
      assert.equal(binarySearch(arr, n), expected);
    }
  );
});
Code In Action

Click the Test Box on the right 👉, then copy the above Code and Test Cases and paste into the same section in Test Box to see the Test in action.