오늘은 병합정렬과 퀵정렬에 대해서 공부해보았다

유형

1. 병합정렬

• 하나의 배열을 두 개의 같은 크기로 나눈다음, 두 개의 정렬된것을 합쳐서 전체가 정렬된 모습으로 나타나는 방법
• 병합정렬은 분할, 정복, 결합의 단계가 있다.
  • 분할: 대상이 되는 배열을 같은 크기의 2개의 배열로 나눈다.
  • 정복: 나뉜 배열을 정렬한다. 나뉜 배열의 크기가 너무 크면 다시 분할한다.
  • 결합: 정렬이 완료 된 배열들을 하나의 배열로 합친다.

병합정렬 과정

1. 배열을 같은 크기로 계속 분할
2. 2개의 리스트씩 서로 비교 후 정렬 후 병합
3. 역순으로 합치면서 나뉜 리스트끼리 정렬 후 병합
4. 최종적으로 2개의 리스트만 남으면 서로 정렬 후 병합

위 그림의 정렬 과정

1. 분할 분할 분할~~
2. n, n+1(n=0, 2, 4, 6)이 서로 비교하여 정렬 후 두개의 값을 가진 하나의 배열로 각각 병합한다.
3. 다시 n, n+1(n=0, 2)이 서로 비교하여 정렬 후 네개의 값을 가진 하나의 배열로 각각 병합한다.
4. 네개의 값을 가진 각각의 배열이 서로 값을 비교하여 정렬 후 병합한다.

code

function mergedSort(arr){
  let length = arr.length;
  let result = [];
  if (length <=1){
    return arr;
  }
  let middleNum = parseInt(length/2);
  let groupOne = mergedSort(arr.slice(0, middleNum));
  let groupTwo = mergedSort(arr.slice(middleNum, ));
  
  while(groupOne.length !== 0 && groupTwo.length !== 0){
    if (groupOne[0] < groupTwo[0]) {
  	  result.push(groupOne.shift());
    } else {
      result.push(groupTwo.shift())'
    }
  }
  
  while(groupOne.length !== 0){
    result.push(groupOne.shift());
  }
  
  while(groupTwo.length !== 0){
    result.push(groupTwo.shift());
  }
  
  return result;
}

2. 퀵정렬

• 퀵 정렬은 피벗이라는것이 있다. 배열안에 있는 값 하나를 선택해서 기준점으로 잡는것이다.

퀵정렬 과정

1. 피벗을 하나 선택한다.
2. 피벗보다 큰 값들은 오른쪽, 작은 값들은 왼쪽으로 옮긴다.
3. 피벗을 제외한 왼쪽과 오른쪽 배열들을 각각 정렬한다.
4. 배열의 크기가 0이나 1이 될때까지 반복한다.

code

function quickSort(arr) {
  let length = arr.length;

  if (length <= 1) {
    return arr;
  }

  let pivot = [arr.shift()];
  let groupOne = [];
  let groupTwo = [];

  for (const i in arr) {
    if (arr[i] < pivot) {
      groupOne.push(arr[i]);
    } else {
      groupTwo.push(arr[i])
    }
  }
  return quickSort(groupOne).concat(pivot, quickSort(groupTwo))
}