Sorting Algorithms

Dallas Baker -

Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. Selection sort accomplishes this by finding the minimum value and pushing it to a new array. Selection sort maintains two arrays.

  1. New sorted Array
  2. Original Unsorted Array

Selection Sort is iterative in nature and has a time complexity of O(n 2) which makes it inefficient for big data.

function selectionSort(array) {
  let n = array.length;
  for (let i = 0; i < n; i++) {
    let min = i;
    for (let j = i + 1; j < n; j++) {
      if (array[j] < array[min]) min = j;
    }

    let temp = array[min];
    array[min] = array[i];
    array[i] = temp;
  }
}

Bubble Sort

Probably the simplest sorting algorithm bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. Time complexity is O(n^2)

function bubbleSort(array) {
  let n = array.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

Insertion Sort

Insertion Sort works much like how we sort playing cards in our hand.
Upon iteration, if the key is less than the previous element then the element gets pushed to the right and the key takes its place.

function insertionSort(arr) {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    const j = i-1;

    while (j >= 0; && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j-1;
    }
    arr[j + 1] = key;
  }
}

Heap Sort

Heapsort is a comparison based algorithm and is similar to selection sort where it finds the maximum element and places it at the end. It repeats this process for all remaining elements. Heap sort makes use of the Binary Heap data structure. Binary Heap is a complete binary tree (all levels are filled and all nodes are far left) where items are stored in ascending or descending order. This is also known as the max heap or the min heap

First is to build a MAX heap

Because the largest item is stored at the root of the heap we can replace it with the last item of the heap followed by reducing the size by 1 (repeat while size is greater than 1). Since values in a heap are stored in a particular way we can construct the heap as an array. You can then always find the child elements by taking the parent p and multiplying by 2 and then adding 1 to find the left or 2 to find the right.
leftChild = p*2+1 rightChild = p*2+2

function swap(arr, i, largest) {
  let temp = arr[i];
  arr[i] = arr[largest];
  arr[largest] = temp;
}

// n = size of arr, i =  root
function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  
  if (largest !== i) {
    swap(arr, i, largest);
    heapify(arr, n, largest);
  }
}

Now that my Heap or what is essentially a tree with MAX element being the root i can now sort.

function heapSort(arr) {
  // n = size
  let n = arr.length;
  // i is the parent
  for (let i = n / 2 - 1; i >== 0; i++) {
    heapify(arr, n, i);
  }
  // i is the parent
  for (let i = n - 1; i >== 0; i--) {
    // move root to the end of the array
    swap(arr, i, 0);
    // heapify the reduced size
    heapify(arr, i, 0);
  }
}

The heapSort function above calls the swap function calls swap which replaces the last element into the root and removes the root element (the largest value) and then heapifies the array so that the root element is again the largest. This happens until there is only a parent with no children.

Quick Sort

Quicksort is an efficient divide and conquer sorting algorithm that is about twice as fast as merge or heap sort. Quicksort partitions the array based on the pivot point's proper location in the array. Quicksort finds the pivot points correct location and then recurses for the sub-arrays or partitions. There are different ways to Implement quick sort by choosing a Pivot point. The pivot point serves as a way to find the pivots place in the array.

  • First element
  • Last element
  • Random element
  • Median.

Quicksort states that given an array and a pivot point x place all elements less than x to the left and all elements greater than x to the right.

For example, given array [5,7,1,8,4,9,3] we are going to sort using the last element. Then compare every element to it except itself and if its less than pivot point then perform a swap.
First, we need to instantiate a variable i that will serve as the lowest value. Then j will signify the iteration in the loop.
i = -1
j=0

5 < 3 ? false (do nothing)
7 < 3 ? false (do nothing)
1 < 3 ? true (Increment i by 1 and swap 1 & 5) -> [1, 7, 5, 8, 4, 9, 3]

Do this until you have compared all elements. i + 1 calculates the pivots place in the array. You know have a left and right side.

array [1, 2, 7, 5, 8, 4, 9 ]
recurse the subarray [7, 5, 8, 4, 9] to find new pivot's place.

Code implementation

function partition(arr, left, right, pivot) {

  // increment by 1 when j < pivot.
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < arr[pivot]) {
      swap(arr, i, j); //assuming swap is defined.
      i++;
    }
  }
  
 function quickSort(arr, left, right) {
  if (left < right) {
  
    // pivot on last element
    const pivot = right;
    // partition the array and calculate new pivot for each side.
    const newPivot = partition(arr, left, right, pivot);
    
    // apply the sort on the left elements
    qsort(arr, left, newPivot - 1);
    // apply the sort on the right elements
    qsort(arr, newPivot + 1, right);
  }
}

Merge Sort

Merge sort is a divide and conquer algorithm that splits the array in half recursively. Once all items in the array have been separated it compares each and places them in the correct location.

Array = [4, 5, 1, 7, 2]

  1. Find the middle.
    • middle = Array.length/2
  2. Declare left
    • left = 0..middle
  3. Declare right
    • right = middle + 1..Array.length
  4. Repeat left and right side
    • [4] [5] [1] [7] [2]

Then merge

  1. [4, 5], [7], [1, 2]
  2. [1,2,4,5], [7]
  3. [1,2,3,4,5,7]

Code

function merge(left, right) {
  const sorted = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      sorted.push(left[i]);
      i++;
    } else {
      sorted.push(right[j]);
      j++;
    }
  }
  // Remainders will be added to end of array.
  return sorted.concat(left.slice(i))
      .concat(right.slice(j));
}

function mergeSort(arr) {
  if (arr.length === 1) {
    // return once we hit an array with a single item
    return arr;
  }

  const middle = Math.floor(arr.length / 2); // round down in js
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

Bucket Sort

Bucket sort is a sorting algorithm that places each value in a bucket that has like values. From there insertion sort is used to sort each individual bucket. This sorting algorithm is used when you know the range and for numbers like floats when counting can't be used.

Code coming soon...

Counting Sort

Counting sort sorts the array by counting the number of objects having a distinct value. Then returns an array with a count of objects with a value of its index.

start with count-1 being the index and index being the value. Subtract 1 from count each iteration.
array[7, 5, 4, 3, 2, 5, 7]
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 1 2 3 5 5 7 7 7]
newArray [0 0 0 0 0 0 0 0]

First iteration
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 0 2 3 5 5 7 7 7]
newArray [2 0 0 0 0 0 0 0]

Second iteration
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 0 1 3 5 5 7 7 7]
newArray [2 3 0 0 0 0 0 0]

Third iteration
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 0 1 2 5 5 7 7 7]
newArray [2 3 4 0 0 0 0 0]

Fourth iteration
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 0 1 2 4 5 7 7 7]
newArray [2 3 4 0 5 0 0 0]

Fifth iteration...
index [0 1 2 3 4 5 6 7 8 9]
count [0 0 0 1 2 3 5 7 7 7]
newArray [2 3 4 5 5 0 0 0]

function countingSort(arr) {
  let output = [];
  let countArr = new Array(15).fill(0);

  arr.Foreach((e) => {
    countArr[e] += 1;
  });
  
  for (let i = 1; i <= countArr.length; i++) {
    countArr[i] = countArr[i - 1];
  }
  for (let i = 0; i < arr.length; i++) {
    output[countArr[arr[i]]-1]) = arr[i];
    count[arr[1]] += 1;
  }
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
  
}

Radix Sort

Radix sort is like Counting sort but compares digit by digit starting with the least significant -> most significant digit. Radix actually uses counting sort as a subroutine.
Let's use Radix Sort to sort this array
[145, 70, 35, 90, 832, 124, 2, 9]

Look at the least significant digit
145, 70, 35, 90, 832, 124, 2, 9
Rearrange array by sorting by the least significant digit and then move to the left
70, 90, 832, 2, 124, 145, 35, 9
2, 9, 124, 832, 35, 145, 70, 90
2, 9, 35, 70, 90, 124, 145, 832
The sorted array -> [2, 9, 35, 70, 90, 124, 145, 832]

// Assuming countSort is defined
function radixSort(arr, size) {
    let m = ((arr) => {
        let max = 0;
        arr.forEach((e) => {
            if (e > max) max = e;
        });
        return max;
    });
    
    // p is the placeholder for the significant digit
    for (let p = 1; m/p > 0; p *= 10) {
      //count sort will sort values based on p
      countSort(arr, size, p);
    }
}