11 퀵 정렬

11.1 퀵 정렬 소개

  퀵 정렬은 매우 빠르고 효율적인 정렬 방식이다. 재귀를 통해 해결하기 가장 쉬운 방법 중 하나이다. 우선 기본적으로 데이터를 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 피벗개념을 통해 정렬되는 방식이다. 즉 비교하는 요소가 하나만 있다면 이미 정렬이 된 것이다. 퀵 정렬에 있어서 가장 중요한 개념은 피벗이다. 퀵 정렬은 피벗 포인트라 불리는 단일 요소를 선택하고 이를 기준으로 작업을 수행한다.

  예를 들어 피벗 포인트를 가운데 있는 요소로 정했다면 할 일은 해당 숫자보다 작은 숫자를 왼쪽으로 옮기고 피벗 포인트보다 큰 숫자는 오른쪽으로 옮기는 것이다. 이렇게 된다면 피벗 숫자 하나만큼은 올바른 위치에 정렬이 된다. 중요한것은 그 피벗 포인트 숫자 하나만 옳바른 위치에 정렬된 것이다. 피벗 포인트의 왼쪽과 오른쪽에 위치한 요소들의 정렬상태는 알 수 없다. 하지만 확실한건 피벗 포인트가 가리키는 요소 만큼은 정확한 위치에 정렬되었다는 것이다. 이 작업을 반복하여 배열을 정렬하는 방식이 퀵 정렬이다.

11.2 피벗 helper 함수 구현
  피벗 포인트는 파티션이라고도 불리운다. 배열이 주어지면 특정 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치 하는 함수를 먼저 구현해야 한다. 피벗보다 작은 값들은 모두 왼쪽으로, 피벗보다 큰 값들은 모두 오른쪽으로 이동시킨다. 앞서 말했지만 양쪽 안에서의 순서는 중요하지 않다. 그리고 가장 주의해야 할 점은 피벗이 제자리에서 수행해야 한다는 것이다. 새 배열을 만들어서도 안된다. 즉 피벗 헬퍼 함수는 인덱스를 반환해야 한다. 이 점이 제일 중요한 점이다.

의사코드
1. 피벗 함수는 배열, 시작인덱스, 끝인덱스 즉 세 개의 인수를 받는다.
2. 기본값으로 시작인덱스는 0, 끝인덱스는 배열길이-1 이다.
3. 그 다음 배열 시작 부분에서 피벗을 선택한다.(무작위 선택이 일반적이지만, 편의를 위해 가장 앞에 있는 요소를 피벗으로 지정한다.)
4. 현재의 피벗 인덱스를 변수에 저장한다.
5. 그 후 뒤의 요소들을 비교하여 피벗의 바뀔 위치를 계속해서 확인한다.
6. 확인을 위해 시작부터 끝까지 돌아가는 루프를 만든다.
7. 살펴보는 요소보다 피벗이 클 경우 피벗 인덱스 변수에 +1을 증가시킨 후 현재 살펴보는 요소와 비벗 인덱스의 요소를 교환한다.
8. 그리고 마지막에는 처음 시작했던 피벗 인덱스와 비교를 통해 증가된 피벗 인덱스를 스왑한 후 피벗 인덱스를 반환한다.

function pivotHelper(arr, start = 0, end = arr.length -1){
    function swap(arr, i, j){
        temp = arr[i];
        arr[j] = arr[i];
        arr[i] = arr[j];
    }

    let pivot = arr[start];
    let pivotIndex = start;

    for(let i = start+1 ; i < arr.length ; i++){
        if(pivot > arr[i]){
            pivotIndex++;
            swap(arr,pivotIndex,i);
        }
    }
    swap(arr,start,pivotIndex);
    return pivotIndex;
}

  위 함수를 통해서 피벗 포인트로 지정된 요소 만큼은 정확한 위치에 정렬될 수 있다. 그리고 비벗이 정렬된 위치 즉, 인덱스 번호를 반환하고 이를 활용하여 퀵 정렬 알고리즘을 구현할 수 있다.

function pivotHelper(arr, start = 0, end = arr.length -1){
    function swap(arr, i, j){
        temp = arr[i];
        arr[j] = arr[i];
        arr[i] = arr[j];
    }

    let pivot = arr[start];
    let pivotIndex = start;

    for(let i = start+1 ; i < arr.length ; i++){
        if(pivot > arr[i]){
            pivotIndex++;
            swap(arr,pivotIndex,i);
        }
    }
    swap(arr,start,pivotIndex);
    return pivotIndex;
}






function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){ // 하위 배열이 하나의 요소 길이에 도달햇을 때 멈추는것임
        //하나 남은 요소는 정렬이 된 상태이니까 그대로 반환하면 그 전체 배열을 반환하면 됨
        let pivotIndex = pivotHelper(arr, left, right) //3
        //피벗기준 왼쪽 요소들(피벗은 정렬이 된 상태니 포함시키지 않음)
        quickSort(arr,left,pivotIndex-1);
        //피벗기준 오른쪽 요소들(피벗은 정렬이 된 상태니 포함시키지 않음)
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
}

  퀵 정렬 알고리즘에서 꼭 인지해야 할 부분은 새로운 배열을 만들어 내는 것이 아니라는것이다!! 계속해서 arr배열이 조금씩 바뀌는 정렬되는 것이다!! 즉 쉽게 말해 피벗 기준 왼쪽 요소들이 quickSort재귀함수를 통해서 하나의 요소 길이에 도달하게 되었을 때까지 반복 반복하면서 정렬되고, 그 후 피벗 기준 오른쪽 요소들도 왼쪽 요소들과 마찬가지로 재귀의 재귀를 통해 조금씩 정렬되면서 반환하고 반환하고 정렬이 완료되는 것이다. 그리고 마지막에 모두 정렬된 배열을 반환하는 것이다. 정말 다시 한번 강조하지만 헷갈리면 안되는것이 새로운 배열을 만들어 내는 것이 아니고 인수로 전달된 배열을 피벗과 재귀를 통해 계속해서 변화시켜 정렬시키는 방법이다!!!(이 부분이 가장 헷갈렸었다.)

  퀵 정렬에서 하나 알아야할 특징이 있다면 퀵 정렬은 일반적으로 O(nlog n)시간 복잡도를 가지지만 최악의 경우에는 O(n^2) 시간 복잡도를 가지게 된다. 배열이 모두 정렬되어 있는 상태에서 퀵 정렬 알고리즘을 사용하면 그렇게 될 수 있다.(첫 번째 위치한 요소를 피벗으로 하게 되면 분해하면서 모든 요소들이 한 번씩 피벗이 되기 때문이다.) 그렇게 때문에 중간에 위치해야 할 요소를 피벗으로 시작하면 해당 문제를 해결할 수 있다. 하지만 항상 그렇게 선택하는것은 쉽지 않으므로 완전히 위험에서 벗어날 수는 없다.