Javascript의 QuickSort 알고리즘

안녕하세요 여러분 오늘은 Javascript로 QuickSort 알고리즘을 작성하는 방법을 보여드리겠습니다.

QuickSort는 Divide and Conquer 알고리즘입니다. 요소를 피벗으로 선택하고 선택한 피벗을 중심으로 지정된 배열을 분할합니다. 다양한 방식으로 피벗을 선택하는 다양한 버전의 quickSort가 있습니다.

항상 첫 번째 요소를 피벗으로 선택하십시오.
항상 마지막 요소를 피벗으로 선택(아래 구현됨)
임의의 요소를 피벗으로 선택합니다.
중앙값을 피벗으로 선택합니다.
quickSort의 핵심 프로세스는 partition()입니다. 파티션의 대상은 배열과 배열의 요소 x가 피벗으로 주어지면 x를 정렬된 배열의 올바른 위치에 놓고 모든 더 작은 요소(x보다 작음)를 x 앞에 놓고 모든 더 큰 요소(x보다 큼)를 뒤에 놓습니다. 엑스. 이 모든 것은 선형 시간에 수행되어야 합니다.



코드 부분은 다음과 같습니다.

function QuickSort(Arr){
  if(Arr.length <= 1){
    return Arr;
  }

  const pivot = Arr[Arr.length - 1];
  const leftArr = [];
  const rightArr = [];

  for(let i=0; i < Arr.length-1;i++){
    if(Arr[i] < pivot){
      leftArr.push(Arr[i]);
    }
    else{
      rightArr.push(Arr[i])
    }
  }

  return [...QuickSort(leftArr) ,pivot,...QuickSort(rightArr)];

}

const items = [1,5,2,99,81,100,144,121,91,85,74,10];
console.log(QuickSort(items));

먼저 배열의 길이를 확인하고 1이면 배열을 그대로 반환합니다.

그런 다음 이 경우 마지막 요소인 피벗 요소를 선택합니다.

그런 다음 두 개의 빈 배열 leftarr 및 rightarr을 만들어 요소를 피벗과 비교하고 그에 따라 요소를 배치합니다.

그런 다음 for 루프를 사용하여 배열을 반복하고 for 루프 내부에서 각 요소가 피벗보다 작거나 피벗보다 큰지 확인합니다

.

요소가 피벗보다 작으면 왼쪽 배열로 푸시하고 요소가 피벗보다 크면 요소를 오른쪽 배열로 푸시합니다.

그런 다음 왼쪽 및 오른쪽 배열에 대해 재귀적으로 QuickSort를 호출하여 배열이 완전히 정렬될 때까지 분할합니다.

Output - 
[1,2,5,10,74,81,85,91,99,100,121,144]

저는 데이터 구조와 알고리즘이 처음입니다. 따라서 이 게시물에서 실수를 발견하면 댓글 섹션에서 수정하십시오.
감사합니다

인스 타 그램 -