[javascript] Quick sort !

포스팅 하기 전 메세지 : 여러분들 모두 더위 조심하세요 ~ 

 

지난 학기에서 데이터베이스 수업을 들으며 소팅기법에 대해서 알고 있는 학생들이 두각을 보였다. 버블 소팅, 퀵소팅, 머지소팅, 해쉬테이블 이야기가 난무 하는데 어떤 소팅 기법인지 감이 오지 않았다. 나는 끽 해봐야 자바스크립트 Array.sort() 메서드나 이용해 봤지 내가 직접 소팅을 만들어 본적은 없기에 데이터베이스에서 서치와 정렬이 조금 낯 설게 느껴 졌다. 그래서 오늘 포스팅을 뭘 해 볼까 하다가 주말간 소팅에 대해서 공부해볼까 싶어 이렇게 행동으로 옮긴다. 

 

Quick sort란 

찰스 앤터니 리처드호어가 개발한 정렬 알고리즘으로 배열 내부에 있는 item을 비교해 정렬을 수행하는 비교 정렬이다. - 위키백과발췌

 

퀵 정렬은 n개의 아이템을 정렬할 때 평균 (n log n) 번의 비교를 수행한다.( n 번보다는 높은 복잡도 ) 그러나 최악의 경우 O(n2)(제곱) 의 시간 복잡도를 가진다.

 

  

퀵 소트는 피벗, 분할, 재귀의 개념을 가진다. 먼저 피벗이란 ? 

 

리스트 가운데서 하나의 원소를 고르는데 이를 피벗이라고 한다. (앞으로 해당 배열을 둘로 나눌 때 기준이 된다. . )

 

이 피벗을 기준으로 피벗 앞에는 피벗 보다 값이 작은 원소들이 오고 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이 작업을 분할이라고 한다. 이 분할을 마치고 난 뒤 피벗은 움직이지 않는다. 

 

분할 된 두개의 리스트는 다시 위의 작업을 잘려진 리스트의 길이가 0 , 1 이 될때 까지 재귀적으로 반복된다. 

 

QuickSort시 일어나는 일들 

QuickSort 관련된 글을 보니까 코드의 짜임은 각기 다르지만 결국에는 기존의 배열을 계속해서 쪼개서 피벗 기준 왼쪽에 있는 아이템이 피벗보다 높을때까지 해당 left를 올리고 피벗 기준오른쪽에 있는 아이템이 피벗보다 낮은 아이템을 찾을 때까지 right를 낮춰 해당 item 끼리 교환 하는 작업을 반복 하는 것이다. 

 

뭐 이렇궁 저렇궁 좀 새로운 것 없나 찾다가 zerocho님의 블로그에 있는 예제가 가장 보기 쉬웠고 해당 글을 토대로 Quick sort를 익혀보도록 하겠다. 

 

 

 

 

 

 

 

 

 

피벗을 기준으로 left에는 항상 피벗보다 낮은 수가, right에는 항상 높은 변수가 있어야 한다. 

 

예제

 

function quickSort(array, l, r){
    let right = r ? r : array.length -1; 
    let left = l ? l : 0;
    let pivot = right;
    pivot = partition(array, left, right-1, pivot);
    if(left < pivot -1){
        quickSort(array, left, pivot-1);

    }
    if(pivot +1 < right){
        
        quickSort(array, pivot +1 , right);
    }

    return array;
}

function partition(array, left, right, pivotIndex){
    let pivot = array[pivotIndex];
    console.log(left,right)
    while(left <= right){
        while( array[left] < pivot){
            left++;
        }
        while( array[right] > pivot){
            right--;
        }
        if(left <= right){
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    temp = array[left];
    array[left] = array[pivotIndex];
    array[pivotIndex] = temp;
    console.log(array)

    return left;
}

let array = [4,32,23,7,2,3,6];

array=quickSort(array);

console.log(array)

 

정리하며 

퀵소팅을 하나하나 따라가며 배열의 변화를 지켜보았는데 매우 유익한 내용이였다. 

 

참고 

 

https://eyecandyzero.tistory.com/236

퀵 정렬(Quick Sort) (javascript)

https://www.zerocho.com/category/Algorithm/post/57f72d415141fc5fe4f4ca8b

(Algorithm) 퀵 정렬(quick sort)

https://ko.wikipedia.org/wiki/위키백과

위키백과 - 위키백과, 우리 모두의 백과사전