학습(알고리즘)

퀵정렬은 idx값을 비교해서 왼쪽으로 작은값들을 몰아넣은 후 본인의 idx를 반환하는 헬퍼함수이로 기준이 되는 arr에 직접적으로 관여하기 때문에 idx값을 기준으로 움직인다.
이를 통해 재귀함수로 좌측이 더 작은 값들로만 위치되어있는지를 재귀적으로 쪼개서 순서대로 정렬할 수 있는 함수이며 nlogn의 시간복잡도를 가진다.

 

function pivot(arr, start = 0, end = arr.length - 1) { //계산해주는 피벗함수
  const swap = (arr, idx1, idx2) => {			//위치변경함수
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  
  let pivot = arr[start];	//시작지점부터 확인
  let swapIdx = start;		//시작지점 idx

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIdx++;		//스왑할경우 start값이 위치해야 할 포인트 +1
      swap(arr, swapIdx, i);	//시작값보다 작은경우 왼쪽으로 밀어버리기
    }
  }
  swap(arr, start, swapIdx);//앞에 스왑된 idx들이 추가됨에 따라 시작점 idx와 스왑횟수위치와 교환
  return swapIdx; //정렬기준점 및 정확한 위치(그것보다 작은값은 다 왼쪽으로 밀었으니)인 값의 idx 반환
}


function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){		
        let pivotIndex = pivot(arr, left, right) // idx보다 작은점 왼쪽 큰것 오른쪽 정렬 후 기준점의 좌표
        quickSort(arr,left,pivotIndex-1); //left ~ 기준점-1까지 재귀로 pivot
        quickSort(arr,pivotIndex+1,right); //기준점+1 ~ right까지 재귀로 pivot 
      }
     return arr; //정렬된 경우 리턴
}