[정렬] 퀵정렬

일단 들어가기에 앞서서...

퀵정렬은 나에게 있어 정말 정말 난해한 정렬이었다.

사실 지금도 제대로 이해하고 있지 않은 것 같다.

그래도 지식을 견고히 하기 위해 일단 포스팅 해본다.

 

퀵 정렬은 어마어마하게 빠르다고 해서 붙여진 이름으로

합병정렬과 비슷하게 동작하지만 매우매우 직관적이지 못하다.

 

다만, 컴퓨터의 입장에서는 합병정렬보다 효율적일 수 있는 알고리즘이다.

연산 자체가 캐시 메모리에 최적화되어 CPU의 부하를 줄여주는 특징이 있다고 하는데

일단 그렇다는 키워드만 얻어놓고, 다음에 운영체제를 공부할 때 알고리즘과 엮여서 공부해보면 될 것 같다.

 

---

퀵 정렬(Quick Sort)

출처 - 위키백과

 

 

퀵 정렬은 배열 내 피봇(중심축)을 이용해서 엘리먼트를 정렬하는 정렬 방법인데,

합병정렬과의 차이점은

합병정렬이 기존의 배열을 쪼개서 다시 합치는 알고리즘이라면

퀵 정렬은 기존의 배열 내 엘리먼트를 계속 수정해가며 정렬하는 알고리즘이라는 것이다.

즉, 정렬된 새로운 배열이 리턴되는 것이 아니라, 정렬하고자 하는 배열 자체가 정렬되어 리턴된다.

 

퀵 정렬의 정의는 아래와 같다.

• 퀵 정렬은 합병정렬 처럼 배열의 엘리먼트의 갯수가 0개나 1개라면 이미 정렬이 되었다는 개념으로 접근한다.
• 이 때, 퀵 정렬만의 특수적인 기능인 피봇(pivot) 들어가게 된다. (피봇의 사전적 의미는 중심축이다.)
• 이 피봇이 재귀함수를 통해 적절하게 위치하면서, 배열 내 엘리먼트가 정렬하게 된다.
• 이후 종료조건을 만나면 인수로 입력한 배열이 전부 정렬된다.

 

일단 퀵 정렬에는 피봇함수라는 헬퍼 펑션과 재귀가 같이 사용된다.

재귀는 피봇 함수보다 훨씬 쉬우므로,

일단 피봇 함수에 대해서 알아볼 필요가 있다.

 

그치만 이 피봇 함수가 굉장히 직관적이지 못해서

텍스트로만 읽었을 경우 이해가 오히려 더 어려울 수가 있다.

따라서 피봇 헬퍼 함수의 코드를 먼저 공유한다.

 

피봇 헬퍼 함수 코드

function pivot(arr, start = 0, end = arr.length + 1) {

    function swap(array, i, j) {   // 배열 내 자리를 스왑해주는 내부 함수이다.
        var temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }
    
    var pivot = arr[start]        // 피봇 값이다.
    var swapIdx = start           // (0) 아래서 설명하겠다.
    for(var i = start + 1; i < arr.length; i++) {  // (1) 아래서 설명하겠다.
        if (pivot > arr[i]) {
            swapIdx++
            swap(arr, swapIdx, i)
        }
    }
    swap(arr, start, swapIdx)   // (2) 아래서 설명하겠다.
    return swapIdx              // (3) 아래서 설명하겠다.
}

pivot([4, 8, 2, 1, 5, 7, 6, 3])

글로써 설명하면 이해가 잘 가지 않기에

순서대로 하나하나 컴퓨터가 연산하듯 생각해보자.

 

---

 

첫번째 싸이클

4 > 8은 false이므로 if 바로 두번째 싸이클로 넘어간다.

 

---

 

두번째 싸이클

4 > 2는 true이므로 조건문에 맞는 연산이 이루어진다.

 

---

 

세번째 싸이클

4 > 1 은 true이므로 조건문에 맞는 연산이 이루어진다.

 

---

 

네번째 싸이클 ~ 여섯번째 싸이클

모두 조건이 맞지 않으므로 다음 싸이클으로 넘어간다.

 

---

 

일곱번째 싸이클

4 > 3 은 true이므로 조건문에 맞는 연산이 이루어진다. 배열의 마지막이므로 반복문을 탈출한다.

 

---

 

반복문 탈출 후

이후 남은 코드에 따라 차례대로 연산이 된다.

 

 

즉, 피봇 헬퍼 함수는

피봇이 어느 인덱스에 있는지 알려주고,

그 요소를 해당 위치에 가져다 주는 함수인 것이다.

 

이렇게 피봇 헬퍼 함수가 엘리먼트를 배열 내 자기 위치를 찾아주고, 인덱스를 반환했다면

이 값을 이용해 퀵 소트를 만들어 재귀시키는데, 아래처럼 재귀시킨다.

 

• 쪼개진 하나의 배열에는 0 부터 피봇리턴값을 인수로 넘겨주고,
  (ex) QuickSort(arr, 0, 피봇리턴값 - 1)
• 쪼개진 또 다른 배열에는 피봇리턴값부터 배열의 마지막값을 인수로 넘겨준다.
  (ex) QuickSort(arr, 피봇리턴값 + 1, 배열의 끝)

 

이렇게 되면 배열 내 제자리를 찾은 엘리먼트는 계속 고정될 것이고

정렬이 안된 배열들은 계속 정렬이 될 것이다.

 

 

아래는 위 방법을 이용하여

퀵 정렬 알고리즘을 완성한 것이다.

 

퀵 정렬 완성 코드

// 위의 pivot함수가 함께 선언되었다는 가정하에...

function QuickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {                          // (1) 배열 내 정렬할 엘리먼트가 없다면 재귀 탈출
    let pivotIndex = pivot(arr, left, right)   // (2) 일단 정렬을 하고, 리턴인덱스를 받는다.
    QuickSort(arr, left, pivotIndex - 1)       // (3) 재귀(arr, 0, 피봇값 -1)   
    QuickSort(arr, pivotIndex + 1, right)      // (4) 재귀(arr, 피봇값+1, 배열끝)
  }
  return arr
}

// 재귀할때 pivotIndex -1, pivotIndex + 1과 같이 넣는 이유 :
// 이미 pivotIndex에 위치한 엘리먼트는 정렬된 값이기 때문에 넣을 필요가 없다.

 

---

 

퀵 정렬의 BigO

- 시간복잡도(베스트) : O(n log n)

- 시간복잡도(평균) : O(n log n)

- 시간복잡도(최악) : O(n^2)

- 공간복잡도: O(n log n)

 

 

일단 퀵 정렬은 최악의 경우에 

O(n^2)의 시간복잡도를 가지게 된다.

 

최악의 경우는 배열을 반으로 쪼갤 수 없을때 일어난다.

즉, 이미 정렬된 배열에 사용할 경우 최악의 시간 복잡도를 나타낸다.

(정렬된것은 쪼갤 수 없으므로...)

 

이를 방지하기 위해서

피벗을 맨 왼쪽값이 아니라

임의의 난수값이나 중간값을 취해 사용해서 최적화할 수 있다고 한다.

 

이에 대해 시도를 몇번 해보았다.

pivot을 배열의 중간값으로 수정하여 시도한 결과,

 

일단 알고리즘이 돌아가기는 하는데

왜 그렇게 돌아가는지는 잘 이해는 되지않아서

일단 당분간 퀵정렬은 덮어놓고 다음에 한번 더 진득하게 파볼 예정이다.