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 thannextValue
swap them.if
currentValue
was smaller thannextValue
pass the step and compare the two next values.if
currentValue
was equal tonextValue
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!
Top comments (1)
Bubble Sort, Heap Sort, Merge Sort, Shell Sort, Quick Sort
Some comments have been hidden by the post's author - find out more