강의: 구름에듀 "안경잡이개발자가 알려주는 실전 알고리즘 강좌"
링크: 안경잡이개발자가 알려주는 실전 알고리즘 강좌
(강의는 알고리즘 풀이를 C/C++ 언어로 진행합니다.)

내용 정리 출처

정렬 알고리즘

대체로 알고리즘을 공부할 때 가장 먼저 나오는 개념이 정렬 알고리즘인 이유는 효율성의 차이를 가장 극명하게 보여주기 때문

퀵 정렬

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법

특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 알고리즘

선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터 개수가 많은 상황을 대비하여 일반적인 상황에서 사용하기 매우 어려운 알고리즘

의사코드를 작성한다면?

  1. 피벗을 하나 선택한다.
  2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
  3. 양 방향에서 찾은 두 원소를 교환한다.
  4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.
  5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)
  6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)

코드로 작성한다면?

function swap (i, j, arr) {
    const temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

/**
 * 왼쪽 피벗 방식
 * @param {Array<number>} arr 정렬할 배열
 * @param {number} lo 현재 부분배열에서의 왼쪽
 * @param {number} hi 현재 부분배열에서의 오른쪽
 * @returns 정렬된 arr
 */
function quickSort (arr, left = 0, right = arr.length - 1) {
    if (left >= right) {
      return;
    }

    const mid = Math.floor((left + right) / 2);
    const pivot = arr[mid];
    const partition = divide(arr, left, right, pivot);
   
    quickSort(arr, left, partition - 1);
    quickSort(arr, partition, right);
   
    function divide (arr, left, right, pivot) {
        console.log(`arr: ${arr}, left: ${arr[left]}, pivot: ${pivot}, right: ${arr[right]}`)
        while (left <= right) {
            while (arr[left] < pivot) {
                console.log("left", left);
                left++;
            }

            while (arr[right] > pivot) {
                console.log("right", right);
                right--;
            }

            if (left <= right) {
                console.log(left, right);
                swap(left, right, arr);
                left++;
                right--;
            }
        }

        return left;
    }
   
    return arr;
  }

  quickSort(arr1, 0, arr1.length - 1);
  console.log(arr1);

참고) 코드가 간결하지만 메모리 공간의 낭비가 심한 in place 방식이 아닌 코드

function quickSort (array) {
  if (array.length < 2) {
    return array;
  }
  const pivot = [array[0]];
  const left = [];
  const right = [];
 
  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else if (array[i] > pivot) {
      right.push(array[i]);
    } else {
      pivot.push(array[i]);
    }
  }
  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);
  return quickSort(left).concat(pivot, quickSort(right));
}
 
const sorted = quickSort([5, 3, 7, 1, 9]);
console.log(sorted);

시간 복잡도

BigO
평균 O(nlog₂n)

  • Worst Case: O(N^2)
  • Best Case: O(log₂n)

장점

  • in place 알고리즘이기 때문에 메모리가 절약
  • 평균 속도가 O(nlog₂n)로 상당히 빠른 편
  • 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable한 정렬

단점

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN