퀵 정렬

퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다. 이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다

특징

• 퀵 정렬은 크게 두 가지 분할 방법이 있다.
  1.Lomuto's Partition
  2.Hoare's Partition

• Divide and Conquer 전략을 사용한 알고리즘

• 시간 복잡도
  평균의 경우 : O(NlongN)
  최악의 경우 : O(N^2)
  

1.Lomuto's Partition

• 기준이 되는 요소 하나를 pivot으로 설정한 후, 그 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누고 이를 재귀로 반복하여 합치는 방식이다.

• 분할 : 입력 배열을 피벗을 기준으로 비균하게 2개의 부분배열로 분할

• 정복 : 부분배열을 정렬

• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병

function quickSort (array) {
	if (array.length < 2) { // 나누어진 배열의 요소가 하나만 남을때 까지!
    	return array
    }
  	const pivot = [array[0]] // 보통 처음의 요소를 선택
    const left = [] // pivot보다 작은 요소를 담을 배열
    const right = [] // pivot보다 큰 요소를 담을 배열
    
    for (let i = 1; i < array.length; i++) {
    	if (array[i] < pivot) {
        	left.push(array[i])
        }
      	else if (array[i] > pivot) {
        	right.push(array[i])
        }
      else {
      	pivot.push(array[i]) //같을 경우 
      }
    } // pivot이 기준이므로 1부터 시작!
  	return quickSort(left).concat(pivot, quickSort(right)); // 그림대로 요소가 하나만 남을때까지 나누어진 후 합해짐
}

2. Hoare's partition

• 위의 방법은 메모리 공간의 낭비가 심하기 때문에 이 방법이 더 많이 사용된다

• in place Quick Sort라고도 한다

• unstable(불안정한) 정렬 방법이다. (원소들 중에 중복되는 값이 있는 경우, 정렬 이후에 순서가 초기 순서와 달라질 수 있기 때문)

• 위의 방법과 다르게 start, end 두 포인트를 두어 앞과 뒤에서부터 이동시킴

• start는 배열의 왼쪽에서 오른쪽으로 이동하면서 pivot 보다 크거나 같은 값의 index를 찾는다

• end는 배열의 오른쪽에서 왼쪽으로 이동하면서 pivot보다 작거나 같은 값의 index를 찾는다.

function quickSort(array, left =0, right = array.length-1) {
	if (left >= right) { //기저 조건, 
    	return
    }
  const mid = Math.floor((left + right) /2)
  const pivot = array[mid] //중간점
  const partition = divide(array, left, right, pivot)
  
  quickSort(array, left, partition -1); //재귀, 왼쪽 배열
  quickSort(array, partition, right); // 재귀 오른쪽 배열
  
  function divide (array, left, right, pivot) { // 배열이 나누어지기 시작!
  	while (left <= right) { //처음부터 끝까지
    	while (array[left] < pivot) { // 중간점보다 커질때까지
        	left++ //
        }
      	while (array[right] > pivot) { // 중간점보다 작아질때까지
        	right--;
        }
      if (left <= right) { // 
      	let swap = array[left];
        array[left] = array[right]
        array[right] = swap;
        left++;
        right--
      }
    }
    return left
  }
  return array
}

다른 예시

const quickSort = function (arr) {
   if (arr.length <= 1) return arr;

   const pivot = arr[0]; //중간점
   const left = [];
   const right = [];

   for (let i = 1; i < arr.length; i++) {
     if (arr[i] <= pivot) left.push(arr[i]);
     else right.push(arr[i]);
   }

   const lSorted = quickSort(left);
   const rSorted = quickSort(right);
   return [...lSorted, pivot, ...rSorted];
 };

function quickSort(arr, transform = (item) => item) { //콜백함수를 응용
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) < transform(pivot)) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left, transform);
  const rSorted = quickSort(right, transform);
  return [...lSorted, pivot, ...rSorted];
}
```javascript