자료구조 (Data Structure) 02

 

1. Merge Sort 

2. Quick Sort

3. Heap Sort

 

1. Merge Sort  : 잘게 쪼갠다음 합치는 정렬

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.[1] 상향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다.[2]

시간복잡도 O(nlog₂n)

// Merge Sort
const mergeSort = function (array) {
  if (array.length < 2) return array;
  let pivot = Math.floor(array.length / 2);
  let left = array.slice(0, pivot);
  let right = array.slice(pivot, array.length);

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

function merge(left, right) {
  console.log(`left: ${left}, right: ${right}`);

  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  console.log(`result: ${result}`)
  return result;
}

const list = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(list));

 

2. Quick Sort : 하나를 기준으로 쪼개고 정렬 쪼개고 정렬

pivot 하나를 정해서 pivot을 기준으로 큰것은 오른쪽 작은것은 왼쪽으로 정렬한다. 정렬된것에서 pivot을 정해서 위의 과정을 반복한다.

 

• 시간복잡도
• Worst Case: O(n^2)
• Best Case: O(nlog₂n)

 

const list = [55, 80, 30, 90, 40, 50, 70];

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

  let pivot = array[0];
  let left = [];
  let right = [];

  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else if (array[i] > pivot) {
      right.push(array[i]);
    } else {
      pivot.push(array[i]);
    }
  }

  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);
  return quickSort(left).concat(pivot, quickSort(right));
}

console.log(quickSort(list));

 

3. Heap Sort : Heap 이란 최대값 및 최소값을 찾아내기위해 고안된 완전 이진트리 형태의 자료구조

• 시간 복잡도
• 최선의 경우 : O(n log(n))
• 최악의 경우 : O(n log(n))

 

위키백과: 이진트리 검색결과

 

 

 

let arrLen;

function swap(input, i, j) {
  let temp = input[i];
  input[i] = input[j];
  input[j] = temp;
}

function heapRoot(input, i) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let max = i;

  if (left < arrLen && input[left] > input[max]) {
    max = left;
  }

  if (right < arrLen && input[right] > input[max]) {
    max = right;
  }

  if (max != i) {
    swap(input, i, max);
    heapRoot(input, max);
  }
}

function heapSort(input) {
  arrLen = input.length;

  for (let i = Math.floor(arrLen / 2); i >= 0; i--) {
    heapRoot(input, i);
  }

  for (let i = input.length - 1; i > 0; i--) {
    swap(input, 0, i);
    arrLen--;

    heapRoot(input, 0);
  }
}

let nums = [1, 3, 5, 6, 2, 0, 8, 9, 7, 4];

heapSort(nums); // 힙 정렬 시행
console.log(nums);
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

 

 

https://philosopher-chan.tistory.com/251?category=801755 

5-1 Merge Sort 원리, 시간복잡도

합병 정렬 - 위키백과, 우리 모두의 백과사전

https://mber.tistory.com/30

[javascript] merge sort (병합정렬 자바스크립트 알고리즘) 📊

https://im-developer.tistory.com/135

[JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기 (Quick Sort in JavaScript)

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리 - 위키백과, 우리 모두의 백과사전

https://velog.io/@yujo/JS%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-Sort-66pye5v9

[JS]힙 정렬(Heap Sort)

"Icon made by Pixel perfect from www.flaticon.com"