정렬 알고리즘 - (1)

버블 정렬 - O(n2)

const bubbleSort = (array) => {
  const copyArray = array.slice();
  const length = copyArray.length;

  for (let i = 0; i < length; i++) {
    for (let j = i; j < length; j++) {
      if (copyArray[i] > copyArray[j]) {
        let temp = copyArray[i];
        copyArray[i] = copyArray[j];
        copyArray[j] = temp;
      }
    }
  }

  return copyArray;
};

병합 정렬 - O(nlogn)

const mergeSort = (array) => {
  if (array.length < 2) {
    return array;
  }

  const midIndex = Math.floor(array.length / 2);

  // 분할
  const leftArray = mergeSort(array.slice(0, midIndex));
  const rightArray = mergeSort(array.slice(midIndex, array.length));

  // 병합
  let result = [];

  while (leftArray.length > 0 && rightArray.length > 0) {
    if (leftArray[0] < rightArray[0]) {
      result.push(leftArray.shift());
    } else {
      result.push(rightArray.shift());
    }
  }

  if (leftArray.length > 0) {
    result = result.concat(leftArray);
  }

  if (rightArray.length > 0) {
    result = result.concat(rightArray);
  }

  return result;
};

힙 정렬 - O(nlogn)

class MinHeap { // 최소 힙 클래스
  constructor(arr) {
    this.arr = [];

    arr.forEach((value) => this.push(value));
  }

  isEmpty() {
    return this.arr.length === 0;
  }

  heapify() {
    if (!this.isEmpty()) {
      const length = this.arr.length;

      let index = 0;
      let minIndex = 0;
      let leftIndex, rightIndex;

      while (index < length) {
        leftIndex = MinHeap.getLeftIndex(index);
        rightIndex = MinHeap.getRightIndex(index);

        if (this.arr[leftIndex] && this.arr[leftIndex] < this.arr[index]) {
          minIndex = leftIndex;
        }

        if (this.arr[rightIndex] && this.arr[rightIndex] < this.arr[minIndex]) {
          minIndex = rightIndex;
        }

        if (minIndex !== leftIndex && minIndex !== rightIndex) {
          break;
        }

        this.swap(index, minIndex);
        index = minIndex;
      }
    }
  }

  pop() {
    if (!this.isEmpty()) {
      const value = this.arr.shift();

      if (this.arr.length > 0) {
        this.arr.unshift(this.arr.pop());
        this.heapify();
      }
      return value;
    }
  }

  push(value) {
    this.arr.push(value);

    let index = this.arr.length - 1;
    let parentIndex;

    while (true) {
      parentIndex = MinHeap.getParentIndex(index);

      if (this.arr[parentIndex] > this.arr[index]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  swap(index1, index2) {
    let temp = this.arr[index1];
    this.arr[index1] = this.arr[index2];
    this.arr[index2] = temp;
  }

  static getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  static getLeftIndex(index) {
    return 2 * index + 1;
  }

  static getRightIndex(index) {
    return 2 * index + 2;
  }
}

const heapSort = (array) => {
  const minHeap = new MinHeap(array);
  const result = [];

  while (!minHeap.isEmpty()) {
    result.push(minHeap.pop());
  }

  return result;
};