퀵 정렬 (Quick Sort)

• 합병 정렬과 같은 가정으로 동작합니다. 배열을 최소단위로 분할합니다.
• 피봇(pivot)포인트라고 부르는 단일 요소를 선택 및 수행합니다.
• 피봇 포인트를 다른 요소들과 비교하면서 위치를 고정 시킵니다.
• 자신보다 작은수는 왼쪽 큰수는 오른쪽 양쪽다 정렬은 되있지 않습니다.
• 다시 피봇포인트를 잡아서 비교하면서 위치를 잡습니다.

공부할 때는 피봇 포인트를 0번 요소로 지정하겠지만, 사실 어떤 요소를 해도 상관은 없습니다.
가장 좋은건 배열의 중간값...입니다.

아래의 예시는 배열의 마지막을 피봇으로 사용하는 방법입니다.
간단하 한 줄 요약하면 퀵정렬은 : 피봇 뽑아서 배열 안에서 피봇의 위치를 확정 짓고, 좌측(피봇보다 작은수 모임)과 우측(피봇보다 큰수 모임)에서 각각 또 피봇 정하고 위치 확정 짓고~~~ 반복해주는 것 입니다.

피봇 helper

1. 이 함수는 배열! 시작인덱스! 끝인덱스! 세개의 인수를 받습니다.
   (보통 시작인덱스 = 0, 끝인덱스 = 배열 길이 -1 입니다)
2. 배열의 시작을 피봇으로 잡아줍니다. (사실 어디든 상관 없습니다)
3. 현재의 피벗 인덱스를 변수로 저장
4. 배열을 루프로 돌면서 피벗과 크기를 비교합니다.
5. 피벗보다 큰 값이 나오면 그 이전에 피벗이 위치할 수 있게 위치 변경
6. 피벗 인덱스를 반환합니다.

피봇 helper 함수 구현

// First Version
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;

  for(var i = start + 1; i < arr.length; i++){
    if(pivot > arr[i]){
      swapIdx++;
      swap(arr,swapIdx,i);
    }
  }
  swap(arr,start,swapIdx);
  return swapIdx;
}

// Version with ES2015 Syntax
function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  // Swap the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}

pivot([4,8,2,1,5,7,6,3])


 

퀵 정렬 구현 및 빅오

의사코드
1. 피봇 helper 함수를 호출합니다.
2. 피봇 핼퍼로 피봇인덱스의 위치가 정해지면, 위치 기준으로 좌측과 우측 각각 피봇 helper 함수를 호출합니다.
3. 배열의 수가 1개가 되면 helper 함수의 호출은 멈추고 결과를 도출합니다.

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  // We are assuming the pivot is always the first element
  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }

  // Swap the pivot from the start the swapPoint
  swap(arr, start, swapIdx);
  return swapIdx;
}


function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])




// [4,6,9,1,2,5,3]
// [3,2,1,4,6,9,5]
//        4
//  3,2,1    6,9,5
//      3      6
//  2,1      5  9
//    2
//  1

퀵소트 퀵정렬 의 빅오입니다. 합병 정렬때도 말했지만 퀵소트의 경우, worst case 최악의 상황을 갖고 있습니다. 이는 피벗으로 정한 숫자가 중간이 아니라 가장 끝자리에 위치하는 경우입니다... 이럴 경우 분할 정복의 장점을 사용할 수 없게되죠.