DEV Community

Cover image for Sorting Algorithms in 3 Minutes
mosemet
mosemet

Posted on

Sorting Algorithms in 3 Minutes

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

function swapSort (array) {
    let i, j
    for (i = 0; i < array.length - 1; i++){
        for (j = i + 1; j < array.length; j++){
            if (array[i] > array[j]){
                [array[i], array[j]] = [array[j], array[i]]
            }
        }
    }
    return array
}

Enter fullscreen mode Exit fullscreen mode

Min Sort Algorithm - Custom

Min Sort or Minimum sorting algorithm is a custom algorithm I created when I started studying sorting algorithms. It merely grabs the minimum element within the array, pushes the minimum element into a new array, and also deletes that minimum element from the old array. So it will get a new minimum with each iteration until the new array is sorted. I found it quite handy as it was straightfoward to implement using built-in functions.

function minSort (array) {
    let i, j, result = [], len = array.length
    for (i = 0; i < len; i++){
        for (j = 0; j < len - i; j++){
            if (array[j] === Math.min(...array)){
                result.push(array[j])
                array.splice(j,1)
            }
        }
    }
    return result
}
Enter fullscreen mode Exit fullscreen mode

Selection Sort Algorithm

Selection sort algorithm divides the input list into two parts: a sorted sub-list of items which is built up from left to right at the front (left) of the list and a sub-list of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sub-list is empty and the unsorted sub-list is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sub-list, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sub-list boundaries one element to the right.

function selectionSort(array) {
    let i, j
    for (i = 0; i < array.length - 1 ; i++){
        let min = i  
      for (j = i + 1; j < array.length; j++){
        if (array[j] < array[min]){
          min = j
        }
      }
      if (min !== i){
        [array[i], array[min]] = [array[min], array[i]] 
      }
    }
    return array
  }
Enter fullscreen mode Exit fullscreen mode

Quick Sort Algorithm

Quicksort is an in-place sorting algorithm. It is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.[4] The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Animation:
An animation on how the algorithm works can be found here.

function swap(arr, x, y) {
  [arr[x], arr[y]] = [arr[y], arr[x]];
}
function pivot(arr, left = 0, right = arr.length - 1) {
  let shift = left
  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < arr[left]) swap(arr, i, ++shift);
  }
  swap(arr, left, shift);
  return shift;
}

function quickSort(array, left = 0, right = array.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
  }
  return array
}

Enter fullscreen mode Exit fullscreen mode

Merge Sort Algorithm

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted).
  2. Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. This will be the sorted list.
function merger(arr1, arr2) {
    let i = 0, j = 0, mergedArr = [];
    while (i < arr1.length && j < arr2.length) {
      if (arr1[i] > arr2[j]) mergedArr.push(arr2[j++]);
      else mergedArr.push(arr1[i++]);
    }
    while (i < arr1.length) {
      mergedArr.push(arr1[i++]);
    }
    while (j < arr2.length) {
      mergedArr.push(arr2[j++]);
    }
    return mergedArr;
  }
  function mergeSort(array) {
      if (array.length === 1) return array;
    let middle = Math.floor(array.length / 2);
    let left = mergeSort(array.slice(0, middle));
    let right = mergeSort(array.slice(middle));

    return merger(left, right);
  }
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
tebohom profile image
mosemet

most definitely, for most usecases, I will go for the inbuilt sort functions. But it is important to understand how this were constructed to bolster programming skills.