Quick sort 알고리즘..

Quick Sort

function quickSort(arr) {
	if (arr.length < 2) {
  	return arr;
  }
  
  // quickSort의 초기 배열의 첫 번째 값을 pivot 배열의 첫 번째 요소.
  let pivot = [arr[0]];
  let left = [];
  let right = [];
  
  for (let i =1; i<arr.length; i++ ) {
  	if (pivot < arr[i]) {
    	right.push(arr[i]);
    } else if (pivot > arr[i]) {
    	left.push(arr[i]);
    } else {
    	pivot.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

testArr = [39,2,1,4,6,26,55,12];
console.log('test QuickSort: ', quickSort(testArr));

분할정복 알고리즘을 사용한 정렬로써 알고리즘 이름 대로 빠른 정렬에 속한다.

1. 배열 가운데서 하나의 원소를 고른다. (고른 원소를 피벗이라 함)
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗 기준으로 배열을 둘로 나눈다. (분할 정복)
3. 분할된 두 개의 배열에 대해 재귀적으로 1, 2번을 반복한다.