[정렬알고리즘] 퀵정렬 Node.js 예제

정렬에 대한 공부를 하다가 대표적이고 자주 쓰이는 퀵정렬을 배웠다. 실제로 적용해봐야 기억에 확실히 남을 것 같아서 코드를 작성해봤다. 

[정렬알고리즘] 퀵정렬

1. 퀵정렬이란?

2. 퀵정렬의 예시 

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

1. 퀵정렬이란?

매우 효율적인 정렬 방법중 하나이며 분할 정복 알고리즘 방법을 기반으로 작동한다. 분할 정복 알고리즘이란 큰 문제를 작은 문제로 나누어 해결하는 방식이다. 즉 배열을 pivot 기준으로 비균등한 두 개의 하위 배열로 분할하고, 하위 배열에 대해 퀵정렬을 재귀적으로 호출하여 정렬을 수행한다. 이 과정을 반복하여 배열이 더이상 분할되지 않을 때 까지 정렬한다. 퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가진다. 

 

2. 퀵정렬의 예시

const ranDomScore = [5, 3, 8, 4, 9, 1, 6, 2, 7];

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]);
    }

    console.log('왼쪽배열', left);
    console.log('오른쪽배열', right);
  }

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

const sortedStudents = quickSort(ranDomScore);
console.log('정렬된 정수:', sortedStudents);

이렇게만 보면 작동원리를 확실히 모르겠어서 pivot을 기준으로 나뉘는 왼, 오른쪽 배열을 console로 찍어보았다.

이렇게 보면 또 헷갈리는 부분이 있어서 youtube 강의와 아래 자료를 참고했더니 이해가 됐다. 

의문점: high와 low가 엇갈려서 지난 후, 즉 모든 데이터를 탐색한 후에 pivot과 high를 교환하는 부분이 명확친 않다..
모든 데이터를 검색한 후 pivot은 좌, 우 배열중 하나에 들어가게 되고 그 순서는 알고리즘 설정에 따라 달라진다고 하고,
사실상 5는 pivot이기때문에 배열에서 제외되고 [3,4,1,2] 과 [8,9,6,7]의 형태로 퀵정렬이 들어가야 하는것 아닌가?
그렇다면 다음 퀵정렬에선 각각 pivot은 3, 8이 되어야 말이 된다. 
내가 직접 찍은 콘솔에도 이렇게 나오는데 저 설명이랑 뭐가 다른걸까~~

골머리의 흔적ㅋㅋ

추천글

https://www.youtube.com/watch?v=i-_0ec_k7dY&t=348 

https://velog.io/@devjade/JavaScript%EB%A1%9C-%ED%80%B5%EC%A0%95%EB%A0%ACquick-sort%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

JavaScript로 퀵정렬(quick sort)알고리즘 구현하기