[111일차]퀵정렬 알고리즘(Quick sort)

퀵정렬 알고리즘

퀵정렬 알고리즘 또한 합병정렬과 마찬가지로 분할정복법이다.
임의의 수를 기준으로 좌 우측으로 나누는걸 반복 한다.
같은 분할정복법인 합병정렬 과 비슷해 보일 수 있다.

퀵정렬을 설명하는 수도코드는 단 두줄이다.

1. 기준, 기준보다 큰 수는 기준의 좌측, 기준보다 큰 수는 기준의우측으로 배열을 정렬한다.
2. 그 좌측 우측에다 재귀적으로 1번을 적용한다.

방식이 어떻게 흘러가는지 그림으로 알아보자.

---

요런 배열이 있다.
0번째 인덱스를 기준으로 작은수는 왼쪽 큰수는 오른쪽 으로 정리해보자.

이동하는 방법이 복잡하다. 순서가 있는데,
기준을 정한다 0번째인덱스가 국룰.
비교할 수의 인덱스는 길이 - 1 (끝인덱스) 부터 자리교체가 일어나지 않았을 때만 인덱스가 감소한다.

작으면 왼쪽에다 보낸다 이 보내는과정이 까다로운데,

자리이동이 있다면! 비교할 인덱스의 값은 감소하지않는다
하지만 기준인덱스는 1증가 해야한다

자리이동이 없다면! 비교할 인덱스의 값은 1 감소 해야한다.
하지만 기준인덱스는 증가하지 않는다

이걸 반복해보자.

몇번 안남았다 화이팅화이팅!
포인트는 언제 비교인덱스를 줄이고, 기준인덱스를 늘리는지다
재귀적인 생각은 조금만 배우면 누구나 다 한다.
퀵정렬은 자리를 어떻게 옮겨갈지가 관건이다.
splice를 안쓰고 자리를 옮기는게 이렇게 힘들다!

비교인덱스는 그대로고, 기준인덱스는 1 증가했다.

point! 비교인덱스와 기준인덱스가 같으면 함수를 종료시킨다.

이렇게 한번의 좌측과 우측분할 함수가 끝났다.

좌우측이 이렇게 분리됐다.
좌측엔 4보다 작은 수가, 우측엔 4보다 큰수들이 들어갔다.
이렇게 좌측에 좌 우 분리정렬 함수를 적용, 우측에 좌우분리정렬 함수를적용 즉,
좌 우 각각 재귀적으로 분리, 정렬을 실행시켜준다.
그림으로는 더이상 못그리겠다.
바로 코드 ㄱ ㄱ

자바스크립트 코드

/* 랜덤배열생성테스트 */
function getRandomArr(minNum, maxNum, arrLength){
  function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min)) + min; //최댓값은 제외, 최솟값은 포함
  }
  let test = [];
  for(let i = 0; i < arrLength; i++){
    test.push(getRandomInt(minNum, maxNum))
  }
 
  return test;
}
 
/* 본코드 */
function QuickSort (arr){
  //좌, 우 나눠주는 함수 선언
  function divide(pivotIdx, compIdx){
    //기준인덱스와 비교인덱스가 다를때까지 반복
      //만약 기준값이 비교인덱스보다 크면
        //비교인덱스 값을 임시로 다른곳에 할당한다
        //기준인덱스의 다음값은 비교인덱스자리로 옮긴다.
        //기준인덱스값은 기준인덱스 + 1 자리로 옮긴다.
        //원래 기준인덱스 였던 자리에 임시로 저장한 비교인덱스값을 놓는다.
        //pivotIdx++;
      //그 외
        //compIdx--;
    while(pivotIdx !== compIdx){
      if(arr[pivotIdx] > arr[compIdx]){
        let temp = arr[compIdx];
        arr[compIdx] = arr[pivotIdx + 1];
        arr[pivotIdx + 1] = arr[pivotIdx];
        arr[pivotIdx] = temp;
        pivotIdx++;
      }else{
        compIdx--;
      }
    }
    return pivotIdx;
  }
  //정렬시켜주는 함수 선언
  function sort(start, end){
    if(start > end)return;//basecase
    //divide(start, end)실행
    //sort(start, 기준값 - 1) 좌측을 정렬한다.
    //sort(기준값 + 1, end) 우측을 정렬한다.
    let pivot = divide(start, end)
    sort(start, pivot - 1);
    sort(pivot + 1, end);
  }
  sort(0, arr.length - 1);
  //test1
  // console.log(divide(0, arr.length))
  return arr;
}
console.log(QuickSort([4, 8, 5, 1, 6, 3, 7, 2]))
console.log(QuickSort(getRandomArr(1, 10000000, 1000000)))

퀵정렬로 배열 100만개를정리하는데 걸렸던시간은 평균 약0.27초였다

20번정도 시도해본듯