퀵 정렬 알고리즘 (Quick Sort Algorithm)

퀵 정렬(Quick Sort)은 분할 정복(divide and conquer) 방식을 사용하여 배열을 정렬하는 알고리즘입니다. 주어진 배열을 기준값(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하고, 분할된 부분 배열에 대해 재귀적으로 정렬을 수행합니다. 그림으로 설명을 드리겠습니다.

그림1

그림2

그림3

그림4

그림1 : 정렬하고자 하는 배열을 맨 오른쪽 끝을 기준으로 잡아서 새로 생성한 배열 2개(좌, 우)에 기준으로 잡은 배열값(맨 마지막 열 값 10부터)보다 작으면 좌측 배열에 넣고, 크면 우측 배열에 넣습니다. 이 부분을 각 좌측 배열과, 우측 배열을 재귀함수를 이용하여 다시 좌우측으로 정렬하는 작업을 반복합니다. 

그림2 : 더이상 좌, 우측 배열로 나눌 데이터가 없는 경우 회귀를 통해서 각 재귀함수 return값으로 정렬을 합니다. 이 그림에서는 맨 마지막 좌측 배열, 기준점, 우측 배열을 하나의 배열을 병합을 하면 2,4가 정렬되고 return 되었을때 바로 윗단계 return의 좌측 재귀함수로 return 됩니다.

그림3 : 이 그림에서는 이전에 넘어온 2,4가 좌측 재귀 함수로 return 되었고, 오른쪽에 이미 정렬되어있는 8을 좌측 배열, 기준점, 우측 배열을 하나의 배열을 병합후 2,4,6,8값을 return 합니다.

그림4 : 이 그림에서는 이전에 넘어온 2,4,6,8가 좌측 재귀 함수로 return 되었고, 좌측 배열, 기준점, 우측 배열을 하나의 배열을 병합후 2,4,6,8,10값을 return 하여 최종적으로 정렬을 완료합니다.

아래는 JavaScript로 구현된 퀵 정렬 알고리즘의 예시입니다

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

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

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

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 사용 예시
const array = [8, 4, 2, 6, 10];
const sortedArray = quickSort(array);
console.log(sortedArray); // [2, 4, 6, 8, 10]

위의 코드에서 quickSort 함수는 퀵 정렬을 수행하는 함수입니다. 주어진 배열을 분할하여 작은 값은 left 배열에, 큰 값은 right 배열에 저장하고, 각각의 부분 배열에 대해 재귀적으로 quickSort 함수를 호출합니다. 이를 통해 분할된 부분 배열이 정렬되며, 최종적으로 왼쪽 부분 배열, 기준값, 오른쪽 부분 배열을 순서대로 합쳐서 정렬된 배열을 반환합니다.

위의 예시 코드를 실행하면 정렬된 배열이 출력됩니다. 퀵 정렬은 평균적으로 좋은 성능을 보이며, 일반적인 상황에서 매우 효과적으로 동작합니다. 그러나 최악의 경우에는 분할이 균등하지 않을 수 있고, 이로 인해 성능이 저하될 수 있습니다. 따라서 퀵 정렬의 성능을 향상시키기 위해 피벗의 선택과 분할 방법을 최적화하는 방법을 사용하기도 합니다.