[Algorithm] QuickSort

😁 QuickSort

 

분할정복 알고리즘

- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

- 불안정 정렬에 속하며, 비교 정렬에도 속한다.

 

오늘도 그림만보고 JS로 구현하기 시작.

자세한 내용은 아래 링크 참고.

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

 

 

😁 QuickSort 오름차순

const arr = [5, 3, 8, 4, 9, 1, 6, 2, 7];

//오름차순
function ascendingSort(arr) {
    let len = arr.length;

    console.log(arr);

    let pivot = arr[Math.floor(len / 2)];
    console.log(pivot);

    if(len <= 1) {
        return arr;
    }

    let lArr = [];
    let rArr = [];

    for(let i=0; i<len; i++) {
        if(pivot > arr[i]) {
            lArr.push(arr[i]);
        } else if(pivot < arr[i]) {
            rArr.push(arr[i]);
        }
    }

    console.log(lArr);
    console.log(rArr);

    console.log('---------');

    return [...ascendingSort(lArr), pivot, ...ascendingSort(rArr)];
}

let ascending = ascendingSort(arr);
console.log('ascending: ', ascending);

// ascending:  (9) [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

😁 QuickSort 내림차순

const arr = [5, 3, 8, 4, 9, 1, 6, 2, 7];

//내림차순
function descendingSort(arr) {
    let len = arr.length;

    if(len <= 1) {
        return arr;
    }

    let pivot = arr[Math.floor(len / 2)];
    let lArr = [];
    let rArr = [];

    for(let i=0; i<len; i++) {
        const data = arr[i];

        if(pivot > data) {
            rArr.push(data);
        } else if(pivot < data) {
            lArr.push(data);
        }
    }

    return [...descendingSort(lArr), pivot, ...descendingSort(rArr)];
}

let descending = descendingSort(arr);
console.log('descending: ', descending);

// descending:  (9) [9, 8, 7, 6, 5, 4, 3, 2, 1]

 

나는 Pivot 을 중간 원소를 선택해서 퀵 정렬 알고리즘을 구현하였지만,

아래의 Code Playgroud 포스팅에서는 Pivot 을 배열의 첫번째 원소를 선택해서 

퀵 정렬 알고리즘을 구현하였다.

 

아직 알고리즘에 대해서 잘몰라서, 어떤게 정답인지는 정확하게 모르겠지만,

Pivot 배열의 첫 번쨰 원소를 선택해서 퀵 정렬 알고리즘을 구현해보았다.

 

[퀵 정렬]

 

1. 기준 원소를 고른다.

2. 배열의 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 

2개의 배열로 분할한다.

3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.

 

- 퀵 정렬은 별도의 메모리 공간이 필요하기 때문에, 데이터의 양이 많을 경우 메모리 낭비가 심하기때문에

잘쓰이지 않는 방법이라고 한다.

- 퀵정렬은 할 경우에 중복되는 데이터는 순차적으로 pivot에 저장하면 되기 때문에 정렬 전 중복 데이터의

순서가 바뀌지 않는 안정한 정렬 구현이 가능하다고 한다.

 

 

const arr = [5, 3, 8, 4, 9, 1, 6, 2, 7, 9, 10];

function ascendingSort(arr) {
    let len = arr.length;

    if(len < 2)  {
        return arr;
    }

    const pivot = [arr[0]];
    let lArr = [];
    let rArr = [];

    for(let i=1; i<len; i++) {
        if(pivot[0] < arr[i]) {
            rArr.push(arr[i]);
        } else if(pivot[0] > arr[i]) {
            lArr.push(arr[i]);
        } else {
            pivot.push(arr[i]);
        }
    }

    return ascendingSort(lArr).concat(pivot, ascendingSort(rArr));
}   

const result = ascendingSort(arr);
console.log('result: ', result);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10]

 

위의 코드는 아래의 블로그를 참고해서 퀵정렬 알고리즘을 구현하였는데,

구현하다보니 위에서 내가 구현한 알고리즘은, Pivot의 값이 중복될 경우

중복되는 데이터는 제거하는 문제가 있었다.

 

그래서, 이번에는 중복된 데이터도 출력되는 완성도가 높아진 퀵정렬을 구현해보았다.

 

 

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

https://im-developer.tistory.com/135

[JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기 (Quick Sort in JavaScript)