Algoritma Sorting dengan JavaScript

Beberapa contoh implementasi algoritma dengan JS.

Bubble Sort

Bubble sort - Wikipedia
function swap(arr, index1, index2) {
  console.log("swapping", arr[index1], arr[index2]);
  const temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

function bubbleSort(arr) {
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = 0; j <= i; j++) {
      console.log("--");
      console.log(`${i}: ${arr[i]}, ${j}: ${arr[j]}`);

      if (arr[i] < arr[j]) {
        swap(arr, i, j);
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2, 5, 4, 2, 1]));

Selection Sort

Selection sort - Wikipedia
function swap(arr, index1, index2) {
  console.log("swapping", arr[index1], arr[index2]);
  const temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

function selectionSort(arr) {
  let indexAngkaTerkecil,
    len = arr.length;

  for (let i = 0; i < len; i++) {
    indexAngkaTerkecil = i;

    for (let j = i + 1; j < len; j++) {
      console.log("--");
      console.log(`${i}: ${arr[i]}, ${j}: ${arr[j]}`);

      if (arr[j] < arr[indexAngkaTerkecil]) {
        indexAngkaTerkecil = j;
      }

      if (indexAngkaTerkecil !== i) {
        swap(arr, i, indexAngkaTerkecil);
      }
    }
  }

  return arr;
}

console.log(selectionSort([2, 5, 4, 2, 1]));

Insertion Sort

Insertion sort - Wikipedia
function insertionSort(arr) {
  for (let i = 0, len = arr.length; i < len; i++) {
    let currentValue = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > currentValue) {

      arr[j + 1] = arr[j]
      j--;
    }

    arr[j + 1] = currentValue;
  }
  return arr;
}

console.log(insertionSort([2, 5, 4, 2, 1]));

Quick Sort

Quicksort - Wikipedia
function quickSort(items) {
  function partition(array, left, right) {
    let pivot = array[Math.floor((right + left) / 2)];
    while (left <= right) {
      while (pivot > array[left]) {
        left++;
      }
      while (pivot < array[right]) {
        right--;
      }
      if (left <= right) {
        var temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left++;
        right--;
      }
    }
    return left;
  }
  function helper(items, left, right) {
    let index;
    if (items.length > 1) {
      index = partition(items, left, right);

      if (left < index - 1) {
        helper(items, left, index - 1);
      }

      if (index < right) {
        helper(items, index, right);
      }
    }
    return items;
  }

  return helper(items, 0, items.length - 1);
}

Merge Sort

Merge sort - Wikipedia
function merge(leftA, rightA) {
  let results = [],
    leftIndex = 0,
    rightIndex = 0;

  while (leftIndex < leftA.length && rightIndex < rightA.length) {
    if (leftA[leftIndex] < rightA[rightIndex]) {
      results.push(leftA[leftIndex++]);
    } else {
      results.push(rightA[rightIndex++]);
    }
  }

  let leftRemains = leftA.slice(leftIndex),
    rightRemains = rightA.slice(rightIndex);

  return results.concat(leftRemains).concat(rightRemains);
}

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }

  let midPoint = Math.floor(array.length / 2),
    leftArray = array.slice(0, midPoint),
    rightArray = array.slice(midPoint);

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

console.log(mergeSort([6, 1, 23, 4, 2, 3]));

Count Sort

Counting sort - Wikipedia
function countSort(array) {
  let hash = {},
    countArr = [];

  for (let i = 0, len = array.length; i < len; i++) {
    if (!hash[array[i]]) {
      hash[array[i]] = 1;
    } else {
      hash[array[i]]++;
    }
  }

  for (const key in hash) {
    for (let i = 0; i < hash[key]; i++) {
      countArr.push(parseInt(key));
    }
  }

  return countArr;
}

console.log(countSort([6, 1, 23, 4, 2, 3]));