JavaScript - QuickSort

 

문제 설명 : 정수를 요소로 갖는 중첩되지 않은 배열을 입력받아서 오름차순으로 퀵 정렬을 이용하여 반환하세요

 

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 퀵 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

let output = quickSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

let output2 = quickSort([5,1,6,3,4,2,7]);
console.log(output2); // --> [1, 3, 21]

 

문제 풀이: 

 

1. 배열 길이가 1이하면 그대로 리턴

2. pivot 변수를 배열의 첫번째 변수로 지정, 다른 알고리즘 예시를 보면 중간이나 끝으로 하는 경우도 본 것 같다. (확인해보삼)
3. left 배열은 빈 배열로 선언

4. right 배열은 빈 배열로 선언 

5. 콜백함수를 반복 순회돌면서 arr[i]보다  trans(pivot)이 작으면 left 배열에 저장
6. 이외의 경우에는 right 배열에 저장
7. 왼쪽 정렬을 재귀호출 

8. 오른쪽 정렬을 재귀호출
9. spread 연산자를 이용해 최종반환 [...왼쪽정렬된 배열, pivot, ...오른쪽 정렬된 배열]

 

function quickSort(arr, trans = (item) => item ) {
  //배열의 길이가 1이하면 arr을 리턴 
  if(arr.length<=1) return arr; 

  //pivot을 입력받은 배열의 첫번째 값으로 지정
  const pivot = arr[0]
  //left 배열을 빈 배열로 선언
  const left = [];
  //right 배열을 빈 배열로 선언 
  const right = [];

  //arr의 길이만큼 순회 
  for(let i=1; i< arr.length; i++){
    //arr의 길이만큼 반복순회하면서 분기처리 
    //trans의 pivot값보다 작으면 left 배열로 저장 
    if(trans(arr[i])<=trans(pivot)){
      left.push(arr[i]);
    }else{
    //trans의 pivot보다 크면 right 배열에 저장 
      right.push(arr[i]);
    }
  }
  console.log("left",left)
  console.log("right",right)
  console.log("pivot",pivot)
  //왼쪽 정렬된 배열에 재귀호출함, left 배열과 콜백함수 trans를 입력
  const lSorted=quickSort(left, trans);
  //오른쪽 정렬된 배열에 재귀호출함, right 배열과 콜백함수 trans를 입력 
  const rSorted=quickSort(right, trans);
  console.log("lsorted",lSorted)
  console.log("rsorted",rSorted)
  console.log("console",[...lSorted, pivot, ...rSorted])
  //pivot이 어떤 값이 되더라도 왼쪽 배열과 오른쪽 배열값이 있기때문에 
  //정렬된 값으로 반환함
  return [...lSorted, pivot, ...rSorted];
 
}

 

 

console.log를 통한 데이터흐름에 대한 로그

left [ 1, 3, 4, 2 ]
right [ 6, 7 ]
pivot 5
left []
right [ 3, 4, 2 ]
pivot 1
left [ 2 ]
right [ 4 ]
pivot 3
lsorted [ 2 ]
rsorted [ 4 ]
console [ 2, 3, 4 ]
lsorted []
rsorted [ 2, 3, 4 ]
console [ 1, 2, 3, 4 ]
left []
right [ 7 ]
pivot 6
lsorted []
rsorted [ 7 ]
console [ 6, 7 ]
lsorted [ 1, 2, 3, 4 ]
rsorted [ 6, 7 ]
console [
  1, 2, 3, 4,
  5, 6, 7
]
[
  1, 2, 3, 4,
  5, 6, 7
]