[JavaSrcipt] 정렬알고리즘 (퀵)

✅ Quick Sort

 

평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 분할 정복 알고리즘의 하나이다.

 

❗ 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.

❗ 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

❗ 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

 

❗ 퀵 정렬의 과정
- 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.

- 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

   (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)

- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
     분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
     부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
     리스트의 크기가 0이나 1이 될 때까지 반복한다.

❗ 퀵 정렬단계

분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열

(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

 

- In place Quick Sort

정렬되지 않은 데이터에서 가운데 원소를 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;
}

console.log(quickSort([6, 3, 8, 5, 2]));

 

먼저 배열의 왼쪽 인덱스와 오른쪽 인덱스의 기본값을 각각 0과 array.length - 1로 설정한다.
그리고 중간 pivot값을 구한다.

 

이제 divide라는 함수를 통해 왼쪽과 오른쪽 인덱스를 이동하며 값을 교환하고 partition으로 설정할 인덱스를 리턴받는다.

리턴받은 partition 인덱스를 기준으로 배열을 왼쪽 배열, 오른쪽 배열로 나눠서 다시 재귀 호출을 한다.

 

 

Big O

- Worst Case: O(n^2)
- Best Case: O(nlog₂n)
퀵 정렬은 대개의 경우 매우 좋은 성능을 보여준다.

최선의 경우에는 스택의 크기가 O(log₂n)이고 각 스택마다 요소의 개수만큼 검색하므로 총 O(n)을 순회하기 때문에

결과적으로 시간 복잡도는 O(nlog₂n)이다.
그러나 최악의 경우에는 스택의 크기가 O(n)이 되고 O(n)번 순회하므로 O(n^2)이란 시간이 소요된다.

quickSort([1, 2, 3, 4, 5, 6, 7]);
quickSort([5, 8, 1, 3, 9, 4, 7]);

이미 정렬된 배열의 경우 7번의 재귀 호출을 한 끝에 정렬이 완료되었으나
뒤섞여있던 배열은 5번의 재귀 호출을 한 끝에 정렬이 완료되었다.

이처럼 이미 정렬된 배열을 첫번재 원소를 기준으로 퀵 정렬하는 경우가 바로 최악의 시나리오이다.
그러나 일반적인 경우에는 최선의 경우와 같은 실행 속도를 가지며 평균적으로 O(nlog₂n) 실행 시간을 가지는

매우 빠른 정렬 방법 중의 하나이며 분할 정복의 좋은 예이다.

 

 

 

-출처

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

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html