What is Sorting?
Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items.
If we've an array of numbers [6, 1, 5 ,8 ,11 ,4]
Maybe we want to sort in ascending order [1, 4, 5, 6, 8 ,11]
Or in a descending order [11, 8, 6, 5, 4, 1]
JavaScript Provide its own Implementation
And because Sorting is commonly needed and used, JavaScript provide its own implementation, so that we don't have to write it from scratch.
// Ascending Order
console.log([6, 1, 5, 8, 11, 4].sort((a, b) => a - b)); // [1, 4, 5, 6, 8 ,11]
// Descending Order
console.log([6, 1, 5, 8, 11, 4].sort((a, b) => b - a)); // [11, 8, 6, 5, 4 ,1]
Why Should we Learn Sorting Algorithms?
If so, why would we learn how to implement a Sorting Algorithms?
It will definitely make you a better programmer, and help you understand how things work behind the scenes.
There're many Sorting Algorithms, In this article we'll discuss the easist two Algorithms, Bubble and Selection.
Most Popular Sorting Algorithms
And here's a list of the most popular Sorting Algorithms:
- Merge Sort
- Quick Sort
- Radix Sort
- Bucket Sort
- Tim Sort
- Insertion Sort
- Bubble Sort
- Selection Sort
Big O Notation
All these Algorithms have different Big O Notation, Varying in difficulty of implementation.
A thing to mention, that JavaScript Default Sort Function uses either Tim or Merge Sort, depending on your Browser.
Swap Function
We'd need a swap function in our Algorithms, So lets start by implementing a Swap function.
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
Bubble Sort
Bubble Sort is the simplest Sorting Algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order, It basically bubbles sorted values to the top.
Here's the first step in Bubble Sort
Repeat the process until the entire array is sorted.
const bubbleSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
};
And here's a visualisation for Bubble Sort Algorithm.
Selection Sort
The selection sort Algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.
Here's the first step in Selection Sort
Repeat the process until the entire array is sorted.
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let swapIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[swapIdx]) {
swapIdx = j;
}
}
swap(arr, i, swapIdx);
}
return arr;
};
And here's a visualisation for Bubble Sort Algorithm.
Happy Coding
Top comments (0)