TIL 23.10.17 (sort)

배열정렬

array = [4,6,2,9,1,3,5,7,8]
sort array.sort((a,b)=>a-b)
array = [1,2,100,3,4]일때 array.sort()하면 [1,100,2,3,4]이런식으로 출력되니 조심
n = array.length;
버블정렬

for (i = 0; i < array.length; i++) {
    for (j = 0; j < array.length; j++) {
        if (array[j] > array[j + 1]) {
            let temp = 0;
            temp = array[j + 1]
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

선택정렬

for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    let temp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = temp;
}

• 삽입 정렬

for (i = 1; i < n; i++) {
    let curvalue = array[i]; 
    let curindex = i - 1; 
    while (curindex >= 0 && array[curindex] > curvalue){ 
    array[curindex + 1] = array[curindex];
        curindex--;
    }
    array[curindex + 1] = curvalue;
}

• 머지 정렬

function Divide(array) {
    let a = array.length

    if (a <= 1) { // 배열의 길이가 1개일때 
        return array;
    }

    let divA = Math.floor(a / 2);
    let left = array.slice(0, divA);
    let right = array.slice(divA, a);
    return Merge(Divide(left),Divide(right));

}
function Merge(left,right){
    let answer = [];
    let leftindex = 0;
    let rightindex = 0;

    while (leftindex < left.length && rightindex < right.length) {
        if (left[leftindex] < right[rightindex]) {
          answer.push(left[leftindex]);
          leftindex++;
        } else {
          answer.push(right[rightindex]);
          rightindex++;
        }
    }
    return answer.concat(left.slice(leftindex)).concat(right.slice(rightindex));
}

sort를 까먹으면 큰일
잊지말자

내일 알고리즘할꺼

• 힙 정렬
• 퀵 정렬
• 셸 정렬
• 기수 정렬