퀵 정렬이란..?

• 분할 정복 알고리즘의 하나이며 평균적으로 빠른 수행 속도가 나온다.
• 시간복잡도는 O(N * logN)이다.
• 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환환 뒤에 배열을 반으로 나누는 것.

분할 정복(divide and conquer)

• 하나의 큰 문제를 작은 2개의 문제로 분할하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 방식

분할(Divide)

입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

정복(Conquer)

부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

순환 호출이 한번 진행 될때마다, 최소한 하나의 원소는 최종 위치가 정해짐 --> 즉 이 알고리즘이 반드시 끝난다는것을 의미함.

퀵 정렬 알고리즘의 개념 요약

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들) 이때 피벗의 왼쪽과 오른쪽의 요소는 정렬되지 않은 상태이지만 피벗보다는 작은것인지 큰것인지는 구분이 가능하다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.(재귀)
4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
5. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
6. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
7. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

알고리즘 예제

배열 [5,4,3,2,1]을 입력받은 후, 해당 배열을 오름차순으로 정렬하여 리턴하는 문제

const quickSort = function (arr ) {
  let pivot = arr[0]  //피벗을 가장 왼쪽에 있는 요소로 지정한다.
  let left = []  // 피벗보다 작은 숫자를 left라는 배열에 담는다.
  let right = [] //피벗보다 큰 숫자를 right라는 배열에 담는다.

  //base case : 배열의 길이가 1이거나 0일 경우에는 비교할만한 요소가 없기때문에 return arr를 해준다.
  if(arr.length <=1) return arr


  //recursive case
  //피벗보다 작은 값은 left에 큰값은 오른쪽에 push
  for(let i =1 ; i<arr.length ; i++){
    if(arr[i] > pivot){
      right.push(arr[i])
    }else {
      left.push(arr[i])
    }
  }


  //left pivot light를 구분 이것을 재귀를 돌린다.
  let recursiveLeft = quickSort(left)
  let recursiveRight = quickSort(right)


  //재귀가 끝난것을 최종적으로 리턴한다.
  return [...recursiveLeft, pivot, ...recursiveRight]


};

참조
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html