JavaScript로 다양한 Sort 구현하기

Bubble sort (버블 정렬)

function bubbleSort(originalArray) {
  let swapFlag = false;

  const sortedArray = [...originalArray];
  const arrayLength = sortedArray.length;
  for (let i = 1; i < arrayLength; i++) {
    swapFlag = false;

    for (let j = 0; j < arrayLength - i; j++) {
      if (sortedArray[j + 1] < sortedArray[j]) {
        [sortedArray[j], sortedArray[j + 1]] = [
          sortedArray[j + 1],
          sortedArray[j]
        ];

        swapFlag = true;
      }
    }

    if (!swapFlag) {
      return sortedArray;
    }
  }

  return sortedArray;
}

 

Selection sort (선택 정렬)

function selectionSort(originalArray) {
  const sortedArray = [...originalArray];
  const arrayLength = sortedArray.length;

  for (let i = 0; i < arrayLength - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arrayLength; j++) {
      if (sortedArray[j] < sortedArray[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [sortedArray[i], sortedArray[minIndex]] = [
        sortedArray[minIndex],
        sortedArray[i]
      ];
    }
  }

  return sortedArray;
}

 

Insertion sort (삽입 정렬)

 

function insertionSort(originalArray) {
  const sortedArray = [...originalArray];
  const arrayLength = sortedArray.length;

  for (let i = 1; i < arrayLength; i++) {
    let minIndex = i;

    for (let j = i; j > -1; j--) {
      if (sortedArray[j] < sortedArray[j - 1]) {
        [sortedArray[j], sortedArray[j - 1]] = [
          sortedArray[j - 1],
          sortedArray[j]
        ];
      } else {
        break;
      }
    }
  }

  return sortedArray;
}

 

---

여기부터 어려워짐

정신 붙들어 매고 이해!

Heap sort (힙 정렬)

 

추가 필요

- https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/heap/Heap.js

- https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/heap/MinHeap.js

- https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/sorting/heap-sort/HeapSort.js

 

Merge sort (병합 정렬)

function mergeSort(originalArray) {
  const arrayLength = originalArray.length;

  if (arrayLength <= 1) {
    return originalArray;
  }

  const middleIndex = Math.floor(arrayLength / 2);
  const leftArray = originalArray.slice(0, middleIndex);
  const rightArray = originalArray.slice(middleIndex, arrayLength);

  const leftSortedArray = mergeSort(leftArray);
  const rightSortedArray = mergeSort(rightArray);

  return mergeArray(leftSortedArray, rightSortedArray);
}

function mergeArray(leftArray, rightArray) {
  const sortedArray = [];

  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
    let minElement = null;

    if (leftArray[leftIndex] <= rightArray[rightIndex]) {
      minElement = leftArray[leftIndex];
      leftIndex += 1;
    } else {
      minElement = rightArray[rightIndex];
      rightIndex += 1;
    }

    sortedArray.push(minElement);
  }

  return sortedArray
    .concat(leftArray.slice(leftIndex))
    .concat(rightArray.slice(rightIndex));
}

 

Quick sort (퀵 정렬)

 

function quickSort(originalArray) {
  if (originalArray.length <= 1) {
    return originalArray;
  }

  const copyedArray = [...originalArray];

  const leftArray = [];
  const rightArray = [];

  const pivotElement = copyedArray.shift();
  const centerArray = [pivotElement];

  while (copyedArray.length) {
    const currentElement = copyedArray.shift();

    if (currentElement === pivotElement) {
      centerArray.push(currentElement);
    } else if (currentElement < pivotElement) {
      leftArray.push(currentElement);
    } else {
      rightArray.push(currentElement);
    }
  }

  const leftArraySorted = quickSort(leftArray);
  const rightArraySorted = quickSort(rightArray);

  return leftArraySorted.concat(centerArray, rightArraySorted);
}