Implement the bubble sort algorithm using TypeScript

#typescript #algorithms #javascript

without any exaggeration, Let's go to the main topic! we start with a question:

what's bubble sort?

bubble sort is a simple sort algorithm to sort a list by scanning and swapping the values in each step if they are in the wrong place (it depends on sort order [ascending/descending]).

Let's go!

in this scenario, we want to sort an array in ascending order.
as we know, an algorithm consists of several specified properties:

Input: an initial value in a specified structure.
Output: the expected value after processing on Input value.
Finiteness: algorithm must stop working after a specified step.
Definiteness: the operations of each step must be specified.
Effectiveness: the instructions must be simple and without any unnecessary actions.

first of all, to obtain the first requirement (input) we have to construct a function that returns an un-sorted array with random numeric values like the below example:

function genRandomArray(arrLength: number) {
  return [...Array(arrLength)].map(() =>
    Math.floor(Math.random() * (100 * arrLength))
  );
}

okay, now we have a dataset generator so let's explain the algorithm:

in this algorithm we have two pointers, like this:

in each step, each value will be compared with its next value:

if currentValue was bigger than nextValue swap them.
if currentValue was smaller than nextValue pass the step and compare the two next values.
if currentValue was equal to nextValue do nothing and the same as the last case, pass it and compare the two next values.
if pointers reach the end of the list: Repeat the algorithm.

End Of Process: these operations are repeated until all of the numbers are fully sorted (if this not make sense, take a look at the following example).

now come to take a look at implemented code:

function bubbleSort(arr: number[]) {
  const cpyArr = [...arr];
  const { length } = cpyArr;

  const swap = (a: number, b: number): void => {
    cpyArr[a] = cpyArr[a] + cpyArr[b];
    cpyArr[b] = cpyArr[a] - cpyArr[b];
    cpyArr[a] = cpyArr[a] - cpyArr[b];
  };

  for (let x = 0; x < length - 1; x++)
    for (let y = 0; y < length - 1 - x; y++) {
      const [currentIndex, nextIndex] = [y, y + 1];
      if (cpyArr[currentIndex] > cpyArr[nextIndex])
        swap(currentIndex, nextIndex);
    }

  return cpyArr;
}

console.log(bubbleSort(genRandomArray(10)));

a short quotes about swapping from Wikipedia:

In computer programming, the act of swapping two variables refers to mutually exchanging the values of the variables.
Usually, this is done with the data in memory.

HINT: if you want to sort the array in descending order, you merely have to change the Greater than operator to smaller than operator in if condition, it makes the algorithm works reverse!

thanks for reading!