QuickSort(퀵정렬) with JavaScript

* node 에서는 기본적으로 class를 사용하지 못하므로 babel을 사용해야 한다. 적용법은 최하단 링크에 있다. 귀찮으면 아래 링크의 git을 clone을 하시면 된다. 

퀵정렬 (출처 : 나무위키)

QuickSort (퀵정렬) : Pivot을 기준으로 좌우 좌측에는 그보다 작은 수만, 우측에는 큰 수만 남기는 방식으로 정렬하는 방법. 평균적인 상황에서 최고의 성능을 가짐. 

구현 방법은 간단하다. (* 오름차순 정렬을 한다고 가정한다. )

1. 전체 범위에서 Pivot을 정한다. Pivot을 기준으로 나뉜 범위를 Partiton 이라고 하겠다.
2. Pivot을 기준으로 작은 수는 왼쪽, 큰 수는 오른쪽으로 넘긴다. 
3. 좌/우측 파티션을 각각 1, 2의 과정을 반복한다.  

---

https://eyecandyzero.tistory.com/236

퀵 정렬(Quick Sort) (javascript)

어떻게 코드를 짤지 참고하다가 위 블로그를 발견했다. 좋더라...

---

const swap = (arr, indexA, indexB) => {
    const tmp = arr[indexA];
    arr[indexA] = arr[indexB];
    arr[indexB] = tmp;
}

const quickSort = (arr, left = 0, right = (arr.length - 1)) => {
    let index;
    if (arr.length > 1) {
        index = partition(arr, left, right);
        if (left < index - 1) quickSort(arr, left, index - 1);
        if (index < right) quickSort(arr, index, right);
    }
    return arr;
}

const partition = (arr, _left, _right) => {
    let pivot = arr[Math.floor((_right + _left) / 2)];
    let left = _left;
    let right = _right;

    // pivot 바로 양 옆 녀석들까지 비교하고 바꿔준다. 
    while (left <= right) {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }
    return left;
}


{
    const arr = [];
    for (let i = 0; i < 20; i++) arr.push(Math.round(Math.random() * 50));
    const set = new Set(arr);
    const ArrayToSort = Array.from(set);

    process.stdout.write('before sort : ');
    console.log(ArrayToSort);
    process.stdout.write('after sort  : ');
    console.log(quickSort(ArrayToSort));
}

 위 블로그에서 본 코드를 기반으로 내가 코딱지만큼 수정했다. 

---

https://eyecandyzero.tistory.com/236

퀵 정렬(Quick Sort) (javascript)

아래 내 깃허브에서 소스를 볼 수 있다. 

https://github.com/iamdap91/basic-data-structure

iamdap91/basic-data-structure

http://jeonghwan-kim.github.io/2016/07/19/babel.html

Babel로 ES6 코드 사용하기