정렬 알고리즘(Quick Sort, Merge Sort)

 

퀵 정렬(Quick Sort)

분할 정복(divide and conquer) 방법을 통한 정렬로, 하나의 pivot(축)을 정해서 이 pivot보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시키는 방법입니다.

• quickSort 함수는 재귀적으로 배열을 분할하고 정렬합니다.
• 분할된 배열은 기준보다 작은 부분과 큰 부분으로 나뉘어서 정렬이 이루어집니다. 

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; // 기저 조건: 배열의 길이가 1 이하면 이미 정렬된 것으로 간주
  }

  var pivot = arr[0]; // 첫 번째 원소를 기준으로 선택
  var left = [];
  var right = [];

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

  return quickSort(left).concat(pivot, quickSort(right));
}

// 예제
var numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
var sortedNumbers = quickSort(numbers);
console.log(sortedNumbers);  // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

 

시간 복잡도

• 최선과 평균의 경우 O(nlogn) 입니다.
• 최악의 경우(정렬이 되어 있는 경우) O(n^2) 입니다.

 

특징

• 한 번 결정된 pivot들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠릅니다.
• Unstable 정렬.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬입니다.

*Stable sort : 정렬했을 때 같은 값은 숫자끼리 상대적인 위치가 유지되는 방식.

 

병합 정렬(Merge Sort)

병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 분할 정복(divide and conquer) 방식입니다. 

• mergeSort 함수는 재귀적으로 배열을 반으로 나누어 정렬합니다.
• merge 함수를 사용하여 정렬된 부분을 병합합니다.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // 기저 조건: 배열의 길이가 1 이하면 이미 정렬된 것으로 간주
  }

  // 배열을 반으로 나누기
  var middle = Math.floor(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);

  // 재귀적으로 나눈 부분 정렬
  var leftSorted = mergeSort(left);
  var rightSorted = mergeSort(right);

  // 정렬된 부분을 병합
  return merge(leftSorted, rightSorted);
}

function merge(left, right) {
  var result = [];
  var leftIndex = 0;
  var rightIndex = 0;

  // 왼쪽과 오른쪽 배열 비교하여 정렬
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 남은 원소들 추가
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

// 예제
var numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
var sortedNumbers = mergeSort(numbers);
console.log(sortedNumbers);  // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

 

 

시간 복잡도

• 최선, 평균, 최악 모두 O(nlogn)입니다.
• 분할할 때 걸리는 시간은 O(n), 병합에 걸리는 시간은 O(n), 그리고 레벨의 수가 O(logn)이므로 전체 레벨의 병합에 걸리는 총시간은 O(nlogn)입니다.

 

특징

• Stable 정렬.
• 정렬하고자 하는 배열의 크기만큼의 추가적인 크기가 요구되기 때문에 Not In-place 정렬입니다.