재귀를 활용한 quickSort, Javascript

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

주의 사항

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

입출력 예시

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

풀이

const quickSort = function (arr) {
	let left = [];
    let right = [];
    let middle = arr[0];
    
    if(arr.length < 2){
    	return arr;
    }
    
    for(let i = 1; i < arr.length; i++){
    	if(arr[i] < middle){
        	left.push(arr[i]);
        } else {
        	right.push(arr[i]);
        }
    }
    let leftResult = quickSort(left);
    let rightResult = quickSort(right);
    return [...leftResult, middle, ...rightResult];
};

기존에 풀었던 bubbleSort와 유사한 문제지만, 재귀를 활용해 풀이한 문제입니다.
left, middle, right 값을 생각해내는 게 중요하고, 경험을 통해 문제를 해결할 수 있었습니다.

마지막 quickSort 재귀를 활용 전 오답이 출력된 걸 확인하고 문제를 해결할 수 있었습니다.