Quick Sort

Quick Sort

1960년에 제안되었으며 이후 많은 사람들이 수정 및 보완하여 완성된 정렬 알고리즘이다.

소개된 지 반 세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다.

 

퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데,

실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다.

 

그러나 in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그다음 in place 방법을 정리하겠다.

 

Basic Quick Sort - Not In Place

퀵 정렬은 지난 Merge Sort에서 소개한 Divide and Conquer 전략을 사용한 알고리즘이다.

즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 있는 배열이므로 모든 배열이 기본 배열이 될 때까지 큰 배열을 나눠야 한다.

 

이때 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다.

그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽엔 큰 값의 배열을 놓는다.

 

pivot 왼쪽에 놓인 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 과정을 반복한다.

결국 기본 단계인 원소가 하나만 있는 배열이 남는다.

 

즉 다음의 논리를 가진 다고 할 수 있다.

1. 기준 원소를 고른다.
2. 배열의 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 2개의 하위 배열로 분할한다.
3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.

위 방법은 in place 방법이 아니기 때문에 별도의 메모리 공간이 필요하므로,

데이터의 양이 많으면 공간적인 낭비가 심해져 실제로는 잘 쓰이지 않는 방법이다.

 

그러나 위의 방법으로 퀵 정렬을 할 경우에 중복되는 데이터는 순차적으로 pivot에 넣으면 되기 때문에 정렬 전 중복 데이터의 순서가 바뀌지 않는 stable 한 정렬을 구현할 수 있다.

 

다음은 위  로직을 코드로 구현한 것이다.

function quickSort (array) {
  if (array.length < 2) {
    return array;
  }
  
  const pivot = [array[0]];
  const left = [];
  const 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));
}

const sorted = quickSort([5, 3, 7, 1, 9]);

console.log(sorted);

 

결과는 다음과 같다.

 

In Place Quick Sort

위의 방법은 이해하기에 훨씬 쉽고 구현도 간단하지만 메모리 공간의 낭비가 심하기 때문에 위 방법보다는 in place 방법이 훨씬 더 많이 사용된다.

 

 

정렬되지 않은 데이터의 중간 위치에 있는 값을 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점이 된다.

 

가장 왼쪽부터 값을 pivot값과 비교하여 pivot보다 큰 값이 나타날 때까지 칸을 오른쪽으로 이동한다.

가장 오른쪽부터 값을 pivot값과 비교하여 pivot보다 작은 값이 나타날 때까지 칸을 왼쪽으로 이동한다.

pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다.

 

왼쪽 인덱스가 오른쪽 인덱스보다 커지면 이동을 멈추고 그 자리에서 두 배열로 갈라서

각 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다.

 

이 방법은 추가적인 공간을 필요로 하지 않기 때문에 메모리 공간이 절약된다는 장점이 있으나,

왼쪽과 오른쪽 값을 교환하는 과정에서 중복 값의 위치가 바뀔 수 있으므로 unstable 한 정렬 방법이다.

 

위 논리를 코드로 구현하면 다음과 같다.

function quickSort (array, left = 0, right = array.length - 1) {
  if (left >= right) {
    return;
  }
  
  const mid = Math.floor((left + right) / 2);
  const pivot = array[mid];
  const partition = divide(array, left, right, pivot);
  
  quickSort(array, left, partition - 1);
  quickSort(array, partition, right);
  
  function divide (array, left, right, pivot) {
    console.log(`array: ${array}, left: ${array[left]}, pivot: ${pivot}, right: ${array[right]}`)
    while (left <= right) {
      while (array[left] < pivot) {
        left++;
      }
      while (array[right] > pivot) {
        right--;
      }
      if (left <= right) {
        let swap = array[left];
        array[left] = array[right];
        array[right] = swap;
        left++;
        right--;
      }
    }
    
    return left;
  }
  
  return array;
}

 

 

이 과정을 손으로 써보았다.

위에 Pivot = 2인 과정은 이미 정렬되어있기 때문에 생략하였다.

 

Big O

퀵 정렬은 대게 O(n log n)이지만,

이미 정렬된 배열을 퀵 정렬할 때 O(n^2)의 시간 복잡도를 가진다.

 

하지만 위에 말했든 O(n log n)의 시간 복잡도는 매우 빠른 속도이며,

여전히 divide and conquer의 좋은 예시이다.

 

 

 

 

 

 

 

 

 

 

 

출처

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

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