자바스크립트: 배열 자르기 및 합치기 (예제: 퀵 정렬, 병합 정렬)

배열 자르기

Array.slice(시작인덱스, 끝인덱스)

시작인덱스를 포함하여, 끝인덱스 바로 직전까지 요소를 배열로 반환합니다.

var arr = [4, 1, 2, 11, 5, 7, 3]
console.log(arr.slice(0, 4))

결과는 [4, 1, 2, 11] 로 인덱스 0부터 4의 바로 직전까지인 3번까지를 배열로 반환합니다.

 

배열 합치기

Array.concat(배열1, 배열2, 배열3, ...)

파라미터는 1개 또는 그 이상 가능합니다. 또한 맨 앞의 배열 뒤에 파라미터 순서대로 정렬됩니다.

 

var arr1 = [1, 6]
var arr2 = ["C", "E"]
var arr3 = [65, 31.2, "A"]

console.log(
    arr1.concat(arr2),
    arr2.concat(arr3),
    arr1.concat(arr2, arr3),
    arr1.concat(arr2, ["FX"], arr3)
)

 

예제 0: 중복을 허용하지 않는 임의의 숫자 추출기 (셔플링 기법 이용)

function numberSampler(maxNum, size) {
    if(maxNum < size){
        alert("size는 maxNum보다 작거나 같아야 합니다.")
        return false
    }
    var arr = []
    for(var i = 0; i < maxNum; i++){
        arr[i] = parseInt(i) + 1
    }

    // Shuffling
    for(var i = 0; i < 10000; i++){
        var tempPos = parseInt(Math.random() * arr.length)
        var tempEl = arr[tempPos]
        arr[tempPos] = arr[0]
        arr[0] = tempEl
    }
    // 배열 자르기 0~ 19(size 직전까지)
    return arr.slice(0, size)
}

console.log(numberSampler(100, 20))

 

예제 1: 퀵 정렬(Quick Sort)

퀵 정렬에 대한 설명은 위키백과 링크를 참고하세요.

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr
    }
    
    var leftArr = [], rightArr = []
    var pivot = arr[0]
    
    for(var i = 1; i < arr.length; i++) {
        if(arr[i] <= pivot) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }
    
    // 배열 합치기
    // Python 3: quickSort(leftArr) + [pivot] + quickSort(rightArr)
    return quickSort(leftArr).concat([pivot], quickSort(rightArr)) 
    
}

var unsortedArr = numberSampler(100, 20)
console.log(unsortedArr, quickSort(unsortedArr))

 

예제 2: 병합 정렬(Merge Sort)

병합 정렬에 대한 설명은 위키백과 링크를 참고하세요.

function mergeSort(arr) {
    var merger = function(iLeft, iRight) {
        var mergedArr = []
        var leftPoint = 0,
            rightPoint = 0

        // case1 - left/right의 포인터가 둘 다 비교하는 배열 내에 있는 경우
        while (iLeft.length > leftPoint && iRight.length > rightPoint) {
            if (iLeft[leftPoint] <= iRight[rightPoint]) {
                mergedArr.push(iLeft[leftPoint])
                leftPoint += 1
            } else {
                mergedArr.push(iRight[rightPoint])
                rightPoint += 1
            }
        }

        // case2 - left 포인터는 아직 left 배열 내에 있는데 right 배열에는 비교 대상이 없는 경우
        // 예를 들어: left는 [0, 2, 5, ...], right는 [1] 인 경우를 생각하면 됨
        while (iLeft.length > leftPoint) {
            mergedArr.push(iLeft[leftPoint])
            leftPoint += 1
        }

        // case3 - case 2의 반대상황
        // 예를 들어: left는 [1], right는 [0, 2, 5, ...] 인 경우를 생각하면 됨
        while (iRight.length > rightPoint) {
            mergedArr.push(iRight[rightPoint])
            rightPoint += 1
        }

        return mergedArr
    }

    var splitter = function(iArr) {
        if (iArr.length <= 1) {
            return iArr
        }

        var mid = parseInt(iArr.length / 2)
        var left = splitter(iArr.slice(0, mid))
        var right = splitter(iArr.slice(mid, iArr.length))

        return merger(left, right)
    }

    // 메인 함수 실행
    return splitter(arr)
}

var unsortedArr = numberSampler(100, 20)
console.log(unsortedArr, mergeSort(unsortedArr))

 

자바스크립트 JavaScript 배열 자르기 배열 합치기 배열 합치는 방법 배열 자르는 방법