퀵 정렬, 병합 정렬, 힙

정렬

비교식 정렬은 한 번에 두개씩 비교하여 교환을 정렬하는 방식이다.

분배식 정렬은 키 값을 기준으로 자료를 여러 개의 부분집합으로 분해하고 분분집합을 정렬하고 -> 전체를 정렬하는 방식이다. 

• 분할(Divide): 배열을 같은 크기의 2개의 배열로 분할한다.
• 정복(Conquer): 분할된 배열을 정렬.
• 결합(Combine): 정렬된 부분 배열을 다시 합침

 

퀵 정렬과 병합 정렬은 둘 다 평균적으로 O(n log n) 성능을  갖는다.

 

[공통점]

• divide and conquer(분할과 정복) 알고리즘에 속한다.
• 탐색할 배열의 크기를 쪼개서 재귀함수로 넘긴다.

[차이점]

• 배열을 분할하는 방식이 서로 다르다. 
• 메모리 공간의 사용량이 다르다.
• 퀵 정렬: 메모리 공간을 사용하지 않는다. 오직 콜 스택을 위한 메모리만 사용된다.
• 병합 정렬: 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 크다.

---

1. 퀵 정렬(Quick sort)

퀵 정렬의 알고리즘은 분할과 재귀로 이루어 진다.

원소 간의 비교만으로 정렬을 수행하는 알고리즘이다.

• 기준값(Pivot)을 중심으로 자료를 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.
• 분할과 정복(Divide and Conquer)라는 작업을 반복하여 수행한다.
• 동일한 값에 대해 기존의 순서가 유지되지 않는 불안정 정렬이다. 

[퀵 정렬 분할 방법 2가지]

1. Lomutos'Partition: 배열의 맨 마지막 값을 pivot으로 정함

2. Hoare'sPartition: 물리적으로 배열의 중간값을 pivot으로 정함

[코드로 알아보기]

const array = [4, 7, 1, 9, 5, 2, 8, 6, 3]
function quickSort(arr){
  if (arr.length <= 1){
    return arr;
  }

  const pivot = arr[0]; //첫번째 인덱스를 pivot으로 정함
  const left = [];
  const right = [];

  for (let i=1; i<arr.length; i++){
    if(arr[i] <= pivot){
      left.push(arr[i]);
    //   console.log('left: ', left);
    } else {
      right.push(arr[i]);
    //   console.log('right: ', right);
    }
  }

  const result = [...left, pivot, ...right]
  return result
}

console.log(quickSort(array));//[1, 2, 3, 4, 7, 9, 5, 8, 6]

1. 배열의 길이가 1과 같거나 작게 될 경우 배열을 바로 리턴한다. 
2. pivot 원소 정하기
3. 배열 안에서 pivot보다 작으면 left / 크면 right 이 과정을 arr.lenght만큼 반복 시킴
4. left와 right가 정해진 상태이면 각각의 배열에서 다시 재귀함수 호출 => 다시 정렬
5. left, pivot, right의 리스트를 리턴시킴

 

[퀵 정렬의 시간 복잡도]

• 평균적으로는 O(nlogn)
• 최악의 경우 O(n^2)

---

 

2. 병합 정렬(Merge sort)

정렬된 집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법이다.

자료를 부분집합으로 분할 하고 해당 부분집합에 대해 작업을 정복하고 부분집합들을 다시 결합하는 분할과 정복 방법을 사용한다. 

• 분할과 정복 방법을 사용한다. 
• 동일한 값에 대해 기존의 순서가 유지되는 안정 정렬이다. 

분할과 정복(Divide and Conquer) 

하나의 큰 문제를 작은 문제로 분리한 뒤 각각을 해결하여, 결과를 모아 원래 문제를 해결하는 방법.
대개 재귀 호출을 이용하여 구현된다.

배열 중 원소를 정한 뒤 피벗 보다 작은 원소들과 큰 원소들로 분할(divide)
나눈 배열들에 대해 재귀적으로 함수를 실행 (피벗을 정하고 다시 그 배열에서 작은 배열로 나누고의 반복)

 

[코드로 알아보기]

참고 사이트 : https://basemenks.tistory.com/13

 

const array = [4, 7, 1, 9, 5, 2, 8, 6, 3]
function mergeSort(arr){
    if (arr.length <= 1){
        return arr;
    }

    const mid = Math.floor(arr.length / 2); //4
    const left = arr.slice(0,mid); // 0부터 4개 [ 4, 7, 1, 9 ]
    const right = arr.slice(mid); //나머지 [ 5, 2, 8, 6, 3 ]

    return merge(mergeSort(left), mergeSort(right)); //다시 한 번 함수 호출
    // 나눠진 배열 안에서 또 다시 분할
}

function merge(left, 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());
    }

    return result;
}

console.log(mergeSort(array));

 

[병합 정렬 시간 복잡도]

• O(n log n)으로 정렬 시간이 일정하다.

병합 정렬 특징]

• 배열의 크기가 크면 시간이 오래걸림
• 배열의 크기가 1 이하가 될 때까지 계속 나눠준다.
• 배열 요소의 크기를 비교 한 후 정렬 => 병합 한다.