자바스크립트 알고리즘 - 퀵정렬 (quick sort)

sonaky47·2019년 9월 20일
1
post-thumbnail

설명

소스코드

/**
 * @see https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
 */
function quickSort(array) {
  if (array.length < 2) return array;

  const pivot = array[0];

  let leftCursor = 1;
  let rightCursor = array.length - 1;
  while(leftCursor <= rightCursor) {
    
    // 왼쪽수가 기준보다 크고 오른쪽 수가 기준보다 작으면 위치를 바꿉니다 (swap)
    if (array[leftCursor] > pivot && array[rightCursor] < pivot) {
      [array[leftCursor], array[rightCursor]] = [array[rightCursor], array[leftCursor]];
      leftCursor++;
      rightCursor--;
    }

    // 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다
    if (array[leftCursor] <= pivot) {
      leftCursor++;
    }

    // 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히
    if (array[rightCursor] >= pivot) {
      rightCursor--;
    }
  }

  [array[0], array[leftCursor-1]] = [array[leftCursor-1], array[0]];
  const left = array.splice(0, leftCursor-1);
  const mid = array.splice(0, 1);
  const right = array;

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


const result = quickSort([5,3,8,4,9,1,6,2,7]);

Github

profile
위메프에서 백엔드 개발자로 일하고 있습니다. 너에게쓰는목소리, 키워드다어이리를 출시했습니다.

5개의 댓글

comment-user-thumbnail
2019년 9월 20일

으앗 result가 [1, 2, 4, 3, 5, 6, 8, 7, 9]가 나옵니다~

2개의 답글
comment-user-thumbnail
2019년 9월 24일

이런 알고리즘이 구체적으로 어느상황에서 쓰이는지 예가 있으면 더 좋았겠네요

답글 달기
comment-user-thumbnail
2020년 1월 23일

[array[leftCursor], array[rightCursor]] = [array[rightCursor], array[leftCursor]];
코드가 swap과 같은 역할을 하는게 신기하네요 !
정확한 문법의 명칭이 뭔지 알 수 있을까요 ??

답글 달기