[Algorithm] Quick Sort

 

정렬 알고리즘 중 quick sort를 공부했다.

 

코딩하는 거니 유튜브를 보고 자바스크립트 코드로 작성해봤다.

function getSortedArr(arr) {
  quickSort(arr, 0, arr.length - 1);
  return arr;
}

function quickSort(arr, l, r) {
  if (l < r) {
    const p = partition(arr, l, r);

    quickSort(arr, l, p - 1);  // *
    quickSort(arr, p + 1, r);  // **
  }
}

 

partition 함수의 반환값은 pivot의 인덱스.

피봇 이전 원소들로 quickSort 재귀, 피봇 이후 원소들로 quickSort 재귀를 돈다.

그러다가 원소가 하나만 남으면 l=r 조건으로 함수가 종료된다.

그리고 가장 오른쪽(r)값이 피봇일 때 피봇의 오른쪽 원소들을을 quickSort 돌려고 할 때 ** l(p+1) > r (p)로 종료조건에 해당돼 종료된다. (이 부분 이해가 안 된다면 링크 클릭!)

function partition(arr, l, r) {
  const pivot = arr[r];
  let i = l - 1;

  for (let j = l; j <= r - 1; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
  return i + 1;
}

배열의 가장 오른쪽 원소를 pivot으로 정한다.

왼쪽부터 pivot전(r - 1)까지 for문을 도는데,

원소가 pivot의 값보다 작거나 같으면 i++을 해주고, i, j의 위치를 바꿔준다.

이 때 j는 for문을 진행하고 있는 인덱스이고, i는 pivot보다 작다고 확정된 최근 원소의 인덱스이다.

for문을 모두 돌면 pivot보다 작은 수들이 왼쪽부터 쌓여있다. 이게 인덱스 l부터 i까지.

for문이 끝나고, 피봇(arr[r])을 arr[i+1]과 위치를 바꾼다. 

그러면, pivot의 왼쪽으로는 모두 pivot보다 작은 값이 되고, 오른쪽으로는 모두 pivot보다 큰 값이 된다.

왼쪽이 정렬됐는지는 알 수 없지만, pivot의 위치는 확정지을 수 있다.

partition 함수는 피봇의 인덱스를 반환한다.

 

그리고 이어서 quickSort함수에서 피봇 이전으로 재귀, 이후로 재귀~~

 

재귀는 말로도 설명하기 힘든데, 글로 쓰려니 더 힘들다...

나중에 내가 이걸 읽고 이해할 수 있을까ㅋㅋㅋ

블로그에 써보는 것은 내 머리속을 정리하기 위함이라, 미래의 나에게도 유튜브를 보는 것을 추천한다!!!

 

 

---

참고📚

유튜브 - [코딩하는 거니] 퀵소트/퀵정렬 5분만에 이해하기

유튜브 - [코드없는 프로그래밍] 코딩테스트 기초 퀵 정렬 quick sort