Sorting Algorithms

async function bubbleSort() {
    var currentArr = primaryArray;

    var sorted = false;

    setAlgorithm({ name: "Bubble Sort" });

    while (!sorted) {
      sorted = true;

      for (var i = 0; i < currentArr.length - 1; i++) {
        if (currentArr[i] > currentArr[i + 1]) {
          var swap1 = currentArr[i];
          var swap2 = currentArr[i + 1];
          currentArr[i] = swap2;
          currentArr[i + 1] = swap1;
          setPrimaryArray([...primaryArray, currentArr]);


          let bar1 = document.getElementById(i).style;
          let bar2 = document.getElementById(i + 1).style;
          bar1.backgroundColor = "#DC143C";
          bar2.backgroundColor = "#6A5ACD";

          await sleep(animationSpeed);


          bar1.backgroundColor = "#222831";
          bar2.backgroundColor = "#222831";

          sorted = false;
        }
      }
      if (sorted) finishedAnimation();
    }
  }

async function heapSort() {
    var arr = primaryArray;

    var length = arr.length;
    var index = Math.floor(length / 2 - 1); //This is always the last parent in a heap
    var lastChild = length - 1;

    setAlgorithm({ name: "Heap Sort"});

    while (index >= 0) {
      heapify(arr, length, index);
      index--;

      setPrimaryArray([...primaryArray, arr]);


      if (index >= 0) {
        let bar1 = document.getElementById(index).style;
        let bar2 = document.getElementById(index + 1).style;
        bar1.backgroundColor = "#DC143C";
        bar2.backgroundColor = "#6A5ACD";

        await sleep(animationSpeed);


        bar1.backgroundColor = "#222831";
        bar2.backgroundColor = "#222831";
      } else {
        await sleep(animationSpeed);
      }
    }

    while (lastChild >= 0) {
      var swap1 = arr[0];
      var swap2 = arr[lastChild];

      arr[0] = swap2;
      arr[lastChild] = swap1;
      heapify(arr, lastChild, 0);
      lastChild--;

      setPrimaryArray([...primaryArray, arr]);


      if (index >= 0) {
        let bar1 = document.getElementById(lastChild).style;
        let bar2 = document.getElementById(0).style;
        bar1.backgroundColor = "#DC143C";
        bar2.backgroundColor = "#6A5ACD";


        bar1.backgroundColor = "#222831";
        bar2.backgroundColor = "#222831";
      } else {
        await sleep(animationSpeed);
      }
    }

    finishedAnimation();
  }

  async function heapify(arr, length, index) {
    //Represents larges node out of the three
    var largest = index;

    //Left Child
    var leftNode = index * 2 + 1;
    //Right Child
    var rightNode = leftNode + 1;

    //Check if left is largest, check if reached end
    if (arr[leftNode] > arr[largest] && leftNode < length) {
      largest = leftNode;
    }

    //Check if right is largest, check if reached end
    if (arr[rightNode] > arr[largest] && rightNode < length) {
      largest = rightNode;
    }

    //Check if parent is still largest, if not: perform a swap
    //between the smallest and the largest
    if (largest != index) {
      var swap1 = arr[index];
      var swap2 = arr[largest];

      arr[index] = swap2;
      arr[largest] = swap1;

      heapify(arr, length, largest);
    }

    return arr;
  }

 function mergeSort(array) {
    setAlgorithm({ name: "Merge Sort"});
    if (array.length <= 1) return array;
    const auxiliaryArray = array.slice();

    //Call helper function with current sliced array
    mergeSortHelper(array, 0, array.length - 1, auxiliaryArray);

    return array;
  }

  async function mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray) {
    if (startIdx === endIdx) return;

    //Get sliced array and recursively divide it untill it has single element arrays
    const middleIdx = Math.floor((startIdx + endIdx) / 2);
    mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray);
    mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray);

    await sleep(animationSpeed);

    doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray);
  }

  //Performs merging
  function doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray) {
    let k = startIdx;
    let i = startIdx;
    let j = middleIdx + 1;

    while (i <= middleIdx && j <= endIdx) {
      if (auxiliaryArray[i] <= auxiliaryArray[j]) {
        //Compare values and overwrite primary array with new sorted array
        mainArray[k++] = auxiliaryArray[i++];
        setPrimaryArray([...primaryArray, mainArray]);
        let bar1 = document.getElementById(k).style;
        let bar2 = document.getElementById(i).style;
        bar1.backgroundColor = "#DC143C";
        bar2.backgroundColor = "#6A5ACD";

        setTimeout(() => {
          bar1.backgroundColor = "#222831";
          bar2.backgroundColor = "#222831";
        }, 800);
      } else {
        //Compare values and overwrite primary array with new sorted array
        mainArray[k++] = auxiliaryArray[j++];
        setPrimaryArray([...primaryArray, mainArray]);
        let bar1 = document.getElementById(k).style;
        let bar2 = document.getElementById(i).style;
        bar1.backgroundColor = "#DC143C";
        bar2.backgroundColor = "#6A5ACD";
        setTimeout(() => {
          bar1.backgroundColor = "#222831";
          bar2.backgroundColor = "#222831";
        }, 200);
      }
    }

    mergeBack(i, j, k, middleIdx, endIdx, mainArray, auxiliaryArray);
  }

  //MergeBack and fill the sorted Array
  function mergeBack(i, j, k, midIndex, endIndex, mainArray, auxiliaryArray) {
    while (i <= midIndex) {
      mainArray[k++] = auxiliaryArray[i++];
      setPrimaryArray([...primaryArray, mainArray]);
    }
    while (j <= endIndex) {
      mainArray[k++] = auxiliaryArray[j++];
      setPrimaryArray([...primaryArray, mainArray]);
    }
  }

function quickSort() {
    setAlgorithm({ name: "Quick Sort" });
    var currentArr = primaryArray;
    var left = 0;
    var right = currentArr.length - 1;

    sort(currentArr, left, right);
    setTimeout(finishedAnimation, 2500);
  }

  async function sort(arr, left, right) {
    if (left < right) {
      var partitionIndex = partition(arr, left, right);

      setPrimaryArray([...primaryArray, arr]);
      await sleep(animationSpeed + 100);

      sort(arr, left, partitionIndex - 1);
      sort(arr, partitionIndex + 1, right);
    }
  }

  function partition(arr, left, right) {
    var pivot = arr[right];
    var i = left - 1;

    for (var j = left; j < right; j++) {
      if (arr[j] < pivot) {
        i++;
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        let bar1 = document.getElementById(i).style;
        let bar2 = document.getElementById(j).style;
        bar1.backgroundColor = "#DC143C";
        bar2.backgroundColor = "#6A5ACD";

        setTimeout(() => {
          bar1.backgroundColor = "#222831";
          bar2.backgroundColor = "#222831";
        }, 200);

        setPrimaryArray([...primaryArray, arr]);
      }
    }

    var temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;

    return i + 1;
  }

 function radixCaller() {
    setAlgorithm({ name: "Radix Sort" });
    var currentArr = primaryArray;
    radixSort(currentArr);
  }

  async function radixSort(arr) {
    const max = getMax(arr);

    for (let i = 0; i < max; i++) {
      let buckets = Array.from({ length: 10 }, () => []);
      for (let j = 0; j < arr.length; j++) {
        buckets[getPosition(arr[j], i)].push(arr[j]);
        var bar = document.getElementById(i).style;
        bar.backgroundColor = "#6A5ACD";
      }

      await sleep(animationSpeed + 300);

      var animArr = [];
      for (var c = 0; c < ARRAYSIZE / 10; c++) {
        animArr.push(randomVals(0, ARRAYSIZE - 1));
      }

      animArr.forEach((val) => {
        var bar = document.getElementById(val).style;
        bar.backgroundColor = "#DC143C";
      });

      var animArr2 = [];
      for (var c = 0; c < ARRAYSIZE / 10; c++) {
        animArr2.push(randomVals(0, ARRAYSIZE - 1));
      }

      animArr2.forEach((val) => {
        var bar = document.getElementById(val).style;
        bar.backgroundColor = "#6A5ACD";
      });

      arr = [].concat(...buckets);
      setPrimaryArray(arr);
    }

    finishedAnimation();

    return arr;
  }

  function getMax(arr) {
    let max = 0;
    for (let num of arr) {
      if (max < num.toString().length) {
        max = num.toString().length;
      }
    }
    return max;
  }

  function getPosition(num, place) {
    var result = Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
    return result;
  }