알고리즘 - 3) 정렬

1) merge sort(병합 정렬)

: 하나의 리스트를 두개의 균등한 크기로 분할하고, 분할된 리스트를 정렬한 후 정렬된 부분리스트를 합하여 전체정렬 리스트로 만드는 것

(분할, 정복, 합병으로 이루어진다)

function mergeSort(arr){
    if(arr.length<=1){
        return arr;
    }
    const mid = Math.floor(arr.length/2);
    const left = arr.slice(0,mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}


function merge(left, right){
    let result = [];

    while(left.legnth&& right.length1){
        if(left[0]<=right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift())
        }
    }
    while(left.length){
        result.push(left.shift())
    }
    while(right.length){
        result.push(right.shift())
    }

    return result;
}

const array = prompt('배열을 입력하시오').split(' ').map(n => parseInt(n, 10));
console.log(mergeSort(array));

 

 

 

 

 

 

 

2)선택정렬

: 매번 가장 작은 것을 선택하여 정렬 (원시적 방법)

 

 

 

3) 삽입 정렬

: 데이터가 거의 정렬되어 있을 때 효과적

 

 

 

4)퀵정렬

: pivot을 사용하여 기준으로 잡고, 그것보다 큰 수와 작은 수를 각각의 위치에 배치(pivot은 호어분할(첫번째 데이터로 잡기)사용 다수)

병합정렬과 같이 빠르다.

function quickSort(arr){
    if(arr.length<=1){
        return arr;
    }
    const pivot = arr[0];
    const left = [];
    const right = [];
    for(let i=1 ; i<arr.length; i++){
        if(arr[i]<=pivot){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

const array = prompt('배열을 입력하세요').split(' ').map(n => parseInt(n, 10));
console.log(quickSort(array));

 

 

 

 

5)계수정렬

: ⓐ데이터의 크기 범위가 제한되어 정수 형태로 표현이 가능할 때

ⓑ(가장 큰 데이터 - 가장 작은 데이터)<100,0000일 때 가능하다.

동일한 값이 여러개 존재할 때 적합하다.

 

 

6)파이썬 라이브러리의 sorted()

:병합 정렬 기반이며 두번째 파라미터에 key(기준)함수 설정이 가능하다.