정렬 알고리즘3 - 퀵 정렬

작동방식

합병 정렬과 같은 가정으로 작동한다.

1. 피벗 포인트라는 요소를 정해서 그 피벗 포인트보다 작은 숫자는 피벗 포인트 왼쪽으로 옮김
2. 피벗포인트보다 큰 숫자는 피벗 포인트 오른쪽으로 옮김.
3. 피벗포인트는 ‘올바른 위치’에 있음.
4. 이 과정을 재귀적으로 반복. 피벗 포인트 왼쪽에 있는 덩어리도, 오른쪽에 있는 덩어리에서도 동일하게 돌아감.
5. 0 또는 1개의 요소를 가진 배열로 나누어질때까지 반복.

퀵 정렬에서는 피벗을 어떻게 정하느냐가 속도에 영향을 준다. 이상적으로 데이터셋의 중간값을 선택하면 좋다. 그러나 정렬해야할 데이터가 어떤지는 알 수 없다. 첫번재 요소, 마지막 요소, 가운데 요소, 랜덤 요소 등으로 선택할 수 있다.

수도코드

1. 피벗 함수를 작성한다. 배열, start idx, end idx 이렇게 3개의 인수를 받는다. start idx는 0, end idx는 -1이다.
2. 배열 시작 부분에서 피벗을 선택. 피벗의 인덱스를 변수로 저장.
3. 배열을 처음부터 끝까지 루프를 돌며 각 요소보다 피벗이 클 경우 피벗 인덱스 변수를 증가시킴.
4. 끝까지 루프를 돌고 현재 요소와 피벗 인덱스의 요소를 교환.

피벗 함수 구현

function pivot(arr, start=0, end=arr.length+1){
  function swap(array, i, j) {   // 스왑함수
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  var pivot = arr[start];   // 피벗을 배열 첫째 요소로 한다.
  var swapIdx = start;      // 스왑인덱스는 0부터 시작

  for(var i = start + 1; i < arr.length; i++){
    if(pivot > arr[i]){       // 루프를 돌면서 요소가 피벗보다 작으면
      swapIdx++;              // 스왑인덱스를 +1 하고
      swap(arr,swapIdx,i);    // 스왑인덱스와 해당 요소를 스왑. 즉 앞으로 보낸다.
    }
  }
  swap(arr,start,swapIdx);   // 피벗(start=0)을 제 위치로 스왑
  return swapIdx;
}

퀵 정렬 구현

1. 전체 배열을 피벗 함수에 넣고
2. 피벗 왼쪽을 재귀적으로 피벗 함수에, 오른쪽도 똑같이 구현.

function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){        // 두개가 같아지면 요소가 하나라는 뜻.
        let pivotIndex = pivot(arr, left, right) //3
        quickSort(arr,left,pivotIndex-1);  // 피벗의 왼쪽을 넣음
        quickSort(arr,pivotIndex+1,right);   // 피벗의 오른쪽도
      }
     return arr;    // 반환.
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])

퀵 정렬의 Big-O

최선의 경우 → O(n log n)

최악의 경우 → O(n^2)

평균의 경우 → O(n log n)

공간복잡도 → O(log n)

배열의 길이가 2배 늘어나면 분할이 1회 늘어남. log n.

각각 분해하는 단계마다 O(n)번 비교를 수행. 피벗을 찾을때.

피벗을 첫번째 값으로 할때 최악의 경우. 이미 오름차순으로 정렬된 데이터.

두가지로 나뉘지 않는다. 늘 모든 값이 피벗보다 크므로 사실상 이중 반복문과 같다.

따라서 피벗을 첫번째 값으로 하지 말고, 차라리 랜덤으로 하는 것이 낫다. 또는 매번 중간에 있는 값을 고른다.

이렇게 하면 최악의 경우를 피할 수 있다.