퀵정렬 이해하기

퀵정렬 함수 과정(수도 코드)

(※ p , left, right는 value 값이 아니라 index 값을 의미한다.)

 

1. 임의의 index 값인 p(pivot)를 지정.

 

2. [left] (맨 왼쪽 값, [0]이 아니라, 범위의 제일 왼쪽값 ex) 5~11 일 경우 [5]가 [left]) 

    [left]와 [p] 자리를 변경.

2-1. p가 left 라면 그대로 자리를 유지한다.

 

3. [p] 를 제외한 나머지 값들을 p의 value를 기준으로 값 비교 후, 위치 이동 [(p보다 작은 무리), (p보다 큰 무리)]

 

4. [p]가 바꾸기 이전의, [left] 값과 다시 자리를 바꾸는게 아니라...... 무조건 p를 p보다 작은 무리의 가장 오른쪽에 위치한 값과 자리를 바꾼다. 

4-1. p보다 큰 값들만 있다면 p의 자리를 [left]에 고정 시킨다. 

 

5. p의 자리는 확고 해졌고, 나머지는 p를 기준으로 재배치 되었다. 따라서 나머지 값들을 가지고 1~4 과정을 반복한다.

 

if 조건 (left < right) 조건이 성립되지 않으면 함수 종료. (서로 비교할 값이 더는 없이 1개만 있다는 의미이자, 정렬완료를 의미)

---

관련 예제

---

<js로 코드 구현하기>

function quickSort(arr) {

  if(arr.length < 2) {

    return arr

  }

  let pivot = arr[arr.length - 1]

  let left = []

  let right = []

  for(let i = 0; i < arr.length - 1; i++) {

    if(arr[i] < pivot) { // pivot 기준으로 left, right 각 push

      left.push(arr[i])

    }else {

      right.push(arr[i])

    }    

  }

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

  // pivot은 냅두고 작은 곳은 작은 곳끼리, 큰 곳은 큰 곳끼리 다시 pivot을 뽑아서 quickSort를 실행한다.

}

const arr = [8, 20, -2, 4, -6, 9, 21, -4, -7]

// 가장 작은 값이 첫 pivot이 되도록하고 돌려봣으나 문제가 없다. // 그저 반복문 횟수만 더 늘어나는듯하다.

console.log(quickSort(arr))

// Worst case = O(n^2)

// Avg case = O(nlogn)

 

<실행결과>