[Udemy 알고리즘] quick 정렬

1. 로직

a. 합병정렬과 마찬가지로 한 개 이하의 요소를 지닌 배열들이 항상 정렬되어 있다는 것을 이용한다.

b. 피벗포인트(pivot)라고 불리는 하나의 요소를 선택하고 이 요소를 기준으로 더 작은 수는 왼쪽, 큰 수는 오른쪽으로 나눈다. 이 때, pivot은 정렬되어 있다.(올바른 위치에 있음).

c. 2번의 과정을 왼쪽, 오른쪽에서 다시 반복한다.

2. 피벗 helper 함수 의사코드

a. 배열, start index, end index 이 세 가지를 파라미터로 함수를 작성한다. 기본값은 start는 0, end는 array.length -1

b. 배열의 첫번째를 피벗으로 선택(이건 배열 끝, 중간 혹은 랜덤으로 정할수도 있다.)

c. 현재의 피벗 인덱스를 변수로 저장.(마지막까지 피벗의 위치를 확인한다)

d. 배열을 반복하는데, 피벗이 현재 요소보다 크면 피벗 인덱스를 증가시킨 후 현재 요소와 피벗 인덱스에 있는 요소를 바꾼다?

e. 현재 요소보다 작으면 아무것도 안 해도 됨.

3. pivot Helper, swap 코드

    function swap(array, index1, index2) {
      [array[index1], array[index2]] = [array[index2], array[index1]];
    }
    //반환하는 값이 pivotIndex인 함수다.
    function pivotHelper(array, start = 0, end = array.length + 1) {
      let pivot = array[start];
      let swapIndex = start;
      for (let i = 1; i < array.length; i++) {
        if (pivot > array[i]) {
          //swapIndex + 1에 위치한 요소가 피벗보다 큰 요소임.
          swapIndex++;
          //그래서 swapIndex++이 되었을 때, swaopIndex에 위치한 요소는
          //pivot보다 더 큰 요소기 때문에 i와 자리 바꿔주면 된다.
          swap(array, swapIndex, i);
        }
      }
      swap(array, start, swapIndex);
      return swapIndex;
    }

4. 퀵 정렬 함수

- 내 코드(이대로 해도 정렬이 되긴 하는데 colt썜이 말한 방식으로 구현하지는 않음)

    function quickSort(array) {
      if (array.length <= 1) return array;
      let firstPivotIndex = pivotHelper(array);
      console.log("--------");
      let leftArr = quickSort(array.slice(0, firstPivotIndex));
      let rightArr = quickSort(array.slice(firstPivotIndex + 1));
      console.log([...leftArr, array[firstPivotIndex], ...rightArr]);
      return [...leftArr, array[firstPivotIndex], ...rightArr];
    }

5. 퀵정렬의 Big O

a. 시간복잡도

• best일 때, 평균일 때 모두 O(N log N), worst일 때 O(N^2)

        i. 퀵 정렬은 정렬의 거의 다 되어 있는 경우 최악의 효율을 보인다. pivotIndex를 배열의 첫 요소로 하기 때문에, 정렬이 되어 있으면 나머지 모든 요소와 비교를 실행하고, left와 right로 나누어지지 않으며 첫번째 요소다음 pivotIndex는 두 번 째 요소이므로 두 번 째부터 다시 정렬을 시작함. 이를 해결하려면 피벗을 첫 번째 요소를 선택하지 말고 무작위로 선택해야 한다.

  b. 공간복잡도

• O (log N),

  6. 얻어가야 할 것

  지금 당장 코드를 스스로 쓸 수 있는 지는 중요한 것이 아니다. 작동방식을 이해하고, 각 단계마다 배열이 어떻게 변하는지를 아는 것이 더 중요하다.