DEV Community

Ivy-Walobwa
Ivy-Walobwa

Posted on

Sorting Algorithms

#javascript #webdev #computerscience

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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)