QuickSort

퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다

 

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
  3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
  3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다. 

 

풀이는 아래와 같다 

 

const quickSort = function (arr) {
    return solution(arr,0,(arr.length-1),0);
};

function solution(arr,L,R,index)
{
    let pivot = Math.floor((R+L)/2);
    let left = L;
    let right = R;
    // 사이클 정렬 
    while(true)
    {
        //left pivot 보다 큰수를 만나거나, pivot을 만나면 stop 
        while(true)
        {
            if((arr[pivot] < arr[left]) || (left == pivot)) 
                break;
            else
                left++;
        }
        //right가 pivot보다 작은수를 만나거나 pivot을 만나면 stop 
        while(true)
        {
            if(arr[right] < arr[pivot] || (right == pivot))
                break;
            else
                right--;
        }
        
        // 이후 left가 right보다 왼쪽에 있으면 교환 
        if(left < right)
        {
            let temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;
            if(left != pivot)
                left ++;
            right --;
        }else
        { 
            if((arr[left] < arr[R]) && (2 <= (R-left))) // 오른쪽 정렬 
                solution(arr,left,R,index)    
            if(arr[L] < arr[right]) // 왼쪽 정렬
                solution(arr,L,right,index)
           
            return arr; 
        }
    }
}