Sorting involves arranging data in a collection based on a comparison algorithm.
There are two general families of sorting algorithms;
1.Linear Sorting - treat the problem of sorting as a single large operation
2.Divide and Conquer - partition data to be sorted into smaller sets that can
be independently sorted.
The performance of sorting algorithms can be measured in terms of:
1.Comparisons - number of times two values of an input array are compared for relative equality.
2.Swaps - number of times two values stored in the input are swapped.
I am going to show you the implementation of 5 sorting algorithms in JavaScript:
- Bubble sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
I found this site really helpful in visualizing these algorithms.
Bubble Sort
This is the simplest.
It works by repeatedly swapping values if they are the wrong position. Higher values are generally to the right and lower values are to the left.
Pseudocode
set swap counter to a truthy value
Repeat until the swap counter is a falsy value
Reset swap counter to a falsy value
Look at each adjacent pair
If two adjacent elements are not in order
Swap them and set swap counter to truthy value
Code
function bubbleSort(arr) {
let swapCounter = 1;
while (swapCounter) {
swapCounter = 0;
for (let i = 0; i < arr.length - 1; i++){
if (arr[i] > arr[i + 1]) {
const swapElement = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = swapElement;
swapCounter = 1;
}
}
}
return arr;
}
let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr))
// >> [11, 12, 22, 25,34, 64, 90]
Performance
Worst case - O(n^2)
Best case - O(n^2)
Selection Sort
It works by finding the smallest unsorted element and add it to the array in the first unsorted location
Pseudocode
Repeat until no sorted element remains:
Search the unsorted part of the data to find the smallest value
Swap the smallest value with the first element of unsorted part
Code
function selectionSort(arr){
for (let i = 0; i < arr.length; i++){
for (let j = i + 1; j < arr.length; j++){
if (arr[j] < arr[i]) {
const swapElement = arr[i];
arr[i] = arr[j];
arr[j] = swapElement;
}
}
}
return arr;
}
let arr = [4, 2, 5, 1, 3];
console.log(selectionSort(arr))
// >> [1, 2, 3, 4, 5]
Performance
Worst case - O(n^2)
Best case - O(n)
Insertion Sort
This algorithm sorts items are they are encoumtered
Pseudocode
Call the first element of the array 'sorted'
Repeat until all the elements are sorted :
Look at the next unsorted element . Insert into the 'sorted' position by
shifting the required number of elements
Code
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++){
let unsorted = arr[i];
let idx = i - 1;
while (idx >= 0 && unsorted < arr[idx]) {
arr[idx + 1] = arr[idx];
idx -= 1;
}
arr[idx + 1] = unsorted;
}
return arr;
}
let arr = [4, 2, 5, 1, 3];
console.log(insertionSort(arr))
// >> [1, 2, 3, 4, 5]
Perfomance
Worst case - O(n^2)
Best case - O(n)
Merge Sort
Works by recursively splitting an array into two, sorting them and then combining these arrays in a sorted order
Pseudocode
Sort the left half of the array (Assuming n > 1)
Sort the right half of the array (Assuming n > 1)
Merge the two halves together
Code
function mergeSort(arr) {
let length = arr.length
// if n is not > 1
// list is considered sorted
if (length === 1) {
return arr;
}
let midIdx = Math.ceil(length / 2);
let leftHalf = arr.slice(0, midIdx);
let rightHalf = arr.slice(midIdx, length);
leftHalf = mergeSort(leftHalf);
rightHalf = mergeSort(rightHalf);
return merge(leftHalf, rightHalf)
}
// merge both halfs
function merge(leftHalf, rightHalf) {
const sorted = []
while (leftHalf.length > 0 && rightHalf.length > 0) {
const leftItem = leftHalf[0]
const rightItem = rightHalf[0]
if (leftItem > rightItem) {
sorted.push(rightItem)
rightHalf.shift()
} else {
sorted.push(leftItem);
leftHalf.shift()
}
}
// if left half is not empty
while (leftHalf.length !== 0) {
sorted.push(leftHalf[0])
leftHalf.shift()
}
// if right half is not empty
while (rightHalf.length !== 0) {
sorted.push(rightHalf[0])
rightHalf.shift()
}
return sorted;
}
let arr = [4, 2, 5, 1, 3];
console.log(mergeSort(arr))
// >> [1, 2, 3, 4, 5]
Performance
Worst case - O(nlogn)
Best case - O(nlogn)
Quick Sort
Pseudocode
Repeat until sorted
Pick a pivot value and partition array
Put all value smaller than pivot to the left and larger values to the right
Perform pivot and partition on the left and the right partition
Code
function swap(arr, leftIndex, rightIndex) {
const temp = arr[leftIndex];
arr[leftIndex] = arr[rightIndex];
arr[rightIndex] = temp;
}
function partition(arr, left, right) {
let pivot = arr[Math.floor((right + left) / 2)], //middle element
i = left, //left pointer
j = right; //right pointer
while (i <= j) {
// while left pointer is less than pivot
// move pointer to the right
while (arr[i] < pivot) {
i++;
}
// while righ pointer is greater than pivot
// move pointer to the left
while (arr[j] > pivot) {
j--;
}
// if left pointer is less than or equal to right pointe
// swap elements
// increment left pointer n decrement right pointer
if (i <= j) {
swap(arr, i, j); //sawpping two elements
i++;
j--;
}
}
return i; // index of left pointer
}
function quickSort(arr, left, right) {
let index;
if (arr.length > 1) {
index = partition(arr, left, right); //index returned from partition
if (left < index - 1) { //more elements on the left side of the pivot
quickSort(arr, left, index - 1);
}
if (index < right) { //more elements on the right side of the pivot
quickSort(arr, index, right);
}
}
return arr;
}
let arr = [4, 2, 5, 1, 3];
console.log(quickSort(arr, 0, arr.length - 1));
// >> [1, 2, 3, 4, 5]
Perfomance
Worst Case - O(n^2)
Best Case - O(nlogn)
Note: Bubble sort, insertion sort and selection sort are linear sorting algorithms while merge sort and quick sort are divide and conquer algorithms.
Happy coding 😉
Top comments (0)