빠른 정렬

퀵 정렬에 대해 무엇을 이해하고 있습니까?
  • 일반적으로 재귀적으로 구현됨
  • 원본 배열을 변경합니다
  • .
  • 이진 트리 반전과 유사한 정신 모델
  • 병합 정렬
  • 과 유사함
  • Divide & Conquer 알고리즘입니다
  • .
  • 2가지 기능으로 구성
  • Main 함수가 배열을 재귀적으로 왼쪽과 오른쪽 절반으로 분할함
  • 왼쪽 및 오른쪽 절반이 배열 인덱스를 통해 결정됨

  • 두 번째 도우미 함수가 스왑을 수행하고 새 피벗 인덱스를 반환합니다.
  • 규칙에 따라 마지막 값은
  • 와 비교할 피벗 값입니다.
  • 현재 루프 인덱스의 값이 피벗 값보다 작은 경우
  • 증분
  • 피벗
  • 의 왼쪽으로 더 작음
  • 피벗
  • 오른쪽으로 더 커짐
  • 마지막으로 피벗 포인트
  • 를 반환합니다.

  • 온라인에서 찾은 최고의 비디오 설명:


  • 시간 복잡도:
  • 최고 : O(nlogn)
  • 평균: O(nlogn)
  • 최악 : O(n^2)

  • 공간 복잡성:
  • O(logn)


  • // 27, 18, 6, 21, 26, 24
    // |
    // i
    // |
    // pivotIndex
    //                    |
    //                    pivotValue
    
    function getPivotPoint(arr, start, end) {
        // by convention we always pick the last element as pivot
        let pivotValue = arr[end];
        // pivot index should at the end hold the larger value compared to pivot
        let pivotIndex = start;
    
        for (let i = start; i < end; i++) {
            // as loing as values on the left of the pivot is smaller in value,
            // we swap the index with the latest updated pivot index
            if (arr[i] < pivotValue) {
                if (i !== pivotIndex) {
                    [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
                }
                pivotIndex++;
            }
        }
    
        // swap the latest updated pivot index with the pivot value itself
        // everything on the right is now larger value than the pivot value
        [arr[end], arr[pivotIndex]] = [arr[pivotIndex], arr[end]];
    
        // return new pivot point
        return pivotIndex;
    }
    function QuickSort(arr, start = 0, end = arr.length - 1) {
        // base case
        if (end > start) {
            const pivot = getPivotPoint(arr, start, end);
            QuickSort(arr, start, pivot - 1);   // do the pivot swap on the left
            QuickSort(arr, pivot + 1, end);     // do the pivot swap on the right
        }
        return arr;
    }
    

    좋은 웹페이지 즐겨찾기