정렬_ 퀵 정렬(Quick Sort)

📒 오늘의 공부

퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)

• 정렬 알고리즘 중 하나로, 평균적으로 매우 빠른 실행 속도를 가지는 알고리즘 중 하나
  1. 배열에서 피벗을 선택
  2. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
  3. 왼쪽과 오른쪽 부분 배열에 대한 재귀적인 퀵 정렬이 끝나면, 정렬된 부분 배열을 합쳐 최종 정렬된 배열 반환

---

💡 피벗(pivot): 정렬 대상 배열을 나눌 때 사용되는 요소. 일반적으로 배열의 첫 번째 요소, 마지막 요소, 또는 배열의 중간 요소를 선택하는 것이 일반적

---

2. 퀵 정렬 구현

퀵 정렬 기본 코드

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

퀵 정렬 과정 구체화 코드

// 함수 정의: 배열을 퀵 정렬하는 함수
function quickSort(arr, start = 0, end = arr.length) {
    // 함수 정의: 배열의 두 요소를 교환하는 함수
    function swap(array, i, j) {
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 함수 정의: 배열의 일부를 피벗을 기준으로 분할하는 함수
    function partition(array, start, end) {
        // 피벗은 배열의 첫 번째 요소로 선택
        let pivot = array[start];
        // swapIdx는 피벗보다 작은 요소들의 마지막 인덱스
        let swapIdx = start;

        // 배열을 탐색하면서 피벗보다 작은 요소들을 swapIdx 위치로 이동
        for (let i = start + 1; i < end; i++) {
            if (pivot > array[i]) {
                swapIdx++;
                swap(array, swapIdx, i);
                // 중간 과정을 콘솔에 출력
                console.log(array);
            }
        }

        // 피벗을 올바른 위치로 이동
        swap(array, start, swapIdx);
        // 중간 과정을 콘솔에 출력
        console.log(array);
        // 피벗의 최종 위치 반환
        return swapIdx;
    }

    // 배열의 크기가 1보다 큰 경우에만 정렬 수행
    if (start < end) {
        // 배열을 피벗을 기준으로 두 부분으로 나누고, 피벗의 최종 위치를 얻음
        const pivotIndex = partition(arr, start, end);
        // 각 부분 배열에 대해 재귀적으로 퀵 정렬 수행
        quickSort(arr, start, pivotIndex);
        quickSort(arr, pivotIndex + 1, end);
    }

    // 정렬된 배열 반환
    return arr;
}

// 퀵 정렬 함수 호출 및 결과 출력
const result = quickSort([4, 8, 2, 1, 5, 7, 6, 3]);
console.log(result);

• 코드 실행 결과
  

3. 퀵 정렬을 사용하는 이유

• 빠른 속도: 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지기 때문에 다른 정렬 알고리즘들과 비교했을 때 속도가 빠르다.

• 제자리 정렬(In-place sorting): 입력 배열 내에서 정렬이 이루어지므로 추가적인 메모리 공간이 필요 없어 메모리를 효율적으로 사용한다.