It Takes All Sorts
Yani
To help me comprehend all the many types of sorting algorithms, I’m breaking down how we can use the few basic ones in this article.
I am reviewing what I learned from the Master the Coding Interview: Data Structures + Algorithms course by Andrei Neagoie. Neagoie is the founder of zerotomastery.io and a Senior Software Developer.
Let’s get started, shall we?
Bubble Sort:
- Elementary algorithm
- It “bubbles” up the largest number
- It’s simple, but the least efficient algorithm
- Space complexity 0(1)
- Time complexity 0(n)
const number = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]function bubbleSort(array) {
const length = array.length;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length; i++) {
if(array[j] > array[j+1]) {
//Swap numbers
let temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
} }
}
bubbleSort(numbers);
console.log(numbers); output:
[0, 1, 2, 4, 5, 6, 44, 63, 87, 99, 283]
Selection Sort:
- Elementary algorithm
- Finds the smallest item through the list and swaps it to the first index
- Space complexity is 0(1)
- Time complexity is 0(n²)
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];function selectionSort(array) { const length = array.length;
for (let i = 0; i < length; i++) {
// set current index as minimum
let min = i;
let temp = array[i];
for (let j = i+1; j < length; j++) {
if (array[j] < array[min]){
// update minimum if current is lower than what we had previously
min = j
}
}
array[i] = array[min];
array[min] = temp;
}
}selectionSort(numbers);
Insertion Sort:
- Elementary algorithm
- Useful for lists that are almost or already sorted
- Useful for small datasets
- Sorting from smallest value
- Time complexity is 0(n)
- Space complexity is 0(1)
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];function insertionSort(array) { const length = array.length for (let i = 0; i < length; i++) {
if (array[i] < array[0]) {
// move number to the first position
array.unshift(array.splice(i, 1)[0]);
} else {
// find where number should go
for (let j = 0; j < i; j++) {
if (array[i] > array[j-1] && array[i] < array[j]) {
// move number to the right spot
array.splice(j, 0, array.splice(i, 1)[0]);
}
}
}
}
}insertionSort(numbers);
console.log(numbers);
Merge Sort:
- Complex algorithm
- Divide and conquer algorithm
- Divide a list in half and then divide each subset into half again, and then divide those sublists into half until you have one item
- Then build like a reverse tree
- Usually not asked in tech interviews, but maybe how to implement
- Time complexity is 0(n log (n))
- Space complexity is 0(n)
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];function mergeSort (array) {
if (array.length === 1) {
return array
}// Split Array in into right and leftconst length = array.length;
const middle = Math.floor(length / 2)
const left = array.slice(0, middle)
const right = array.slice(middle)
console.log('left:', left);
console.log('right:', right); return merge(
mergeSort(left),
mergeSort(right)
)
}function merge(left, right){}const answer = mergeSort(numbers);
console.log(answer);output for mergeSort:
left: [ 99, 44, 6, 2, 1 ]
right: [ 5, 63, 87, 283, 4, 0 ]
left: [ 99, 44 ]
right: [ 6, 2, 1 ]
left: [ 99 ]
right: [ 44 ]
left: [ 6 ]
right: [ 2, 1 ]
left: [ 2 ]
right: [ 1 ]
left: [ 5, 63, 87 ]
right: [ 283, 4, 0 ]
left: [ 5 ]
right: [ 63, 87 ]
left: [ 63 ]
right: [ 87 ]
left: [ 283 ]
right: [ 4, 0 ]
left: [ 4 ]
right: [ 0 ]merge:
[ 99 ] [ 44 ]
[ 2 ] [ 1 ]
[ 6 ] [ 1, 2 ]
[ 44, 99 ] [ 1, 6, 2 ]
[ 63 ] [ 87 ]
[ 5 ] [ 63, 87 ]
[ 4 ] [ 0 ]
[ 283 ] [ 0, 4 ]
[ 5, 63, 87 ] [ 0, 283, 4 ]
[ 1, 44, 99, 6, 2 ] [ 0, 5, 63, 87, 283, 4 ]
[
0, 1, 44, 99, 6,
2, 5, 63, 87, 283,
4]
Quick Sort:
- Complex algorithm
- Divide and conquer algorithm
- Uses pivoting technique to break the main lists into smaller lists
- Usually the best sorting algorithm
- Time complexity is 0(n log (n))
- Space complexity is 0(log(n))
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];function quickSort(array, left, right){
const len = array.length;let pivot;
let partitionIndex; if(left < right) {
pivot = right;
partitionIndex = partition(array, pivot, left, right);
//sort left and right
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
return array;
}function partition(array, pivot, left, right){
let pivotValue = array[pivot];
let partitionIndex = left;for(let i = left; i < right; i++) {
if(array[i] < pivotValue){
swap(array, i, partitionIndex);
partitionIndex++;
}
}
swap(array, right, partitionIndex);
return partitionIndex;
}function swap(array, firstIndex, secondIndex){var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}//Select first and last index as 2nd and 3rd parametersquickSort(numbers, 0, numbers.length - 1);
console.log(numbers);
I hope this helps to give you some clarity as to how some of the basic sorting algorithms work. It’s impossible to go through every single sorting algorithm, as there are a ton.
With that said, to cap this article on a high note, check out some visualization assistance x10! This amusing playlist of different folk dances explains how a specific sorting algorithm works. Whoever created this is brilliant. When still in doubt though, refer to the docs!