[JavaScript] 버블정렬, 선택정렬

1. 정렬

[1] 버블 정렬

전체 배열을 순회하면서 이전 항목이 다른 다음 항목보다 큰 경우 두 항목을 교환

모든 가능한짝을 비교하기 때문에 별로 좋진 않다.

6 1 2 3 4 5 를 정렬하려고 하면 순서는 다음과 같다.

1과 6을 비교 : 1 6 2 3 4 5

2와 6을 비교 : 1 2 6 3 4 5

3과 6을 비교 : 1 2 3 6 4 5 

4와 6을 비교 : 1 2 3 4 6 5

5와 6을 비교 : 1 2 3 4 5 6

//버블 정렬
function random(n){
    let arr = new Array();
    let num;
    let temp;
    for(let i = 0;i<=n; i++){
        arr.push(i);
    }
    for(let i = 0;i <arr.length;i++){
        num = Math.floor(Math.random()*n)
        temp = arr[1];
        arr[1] = arr[num];
        arr[num] = temp;
    }
    return arr;
}


function bubblesort(array){
    const arrlen = array.length;
    for(let i = 0; i<arrlen; i++){
        for(let k = 0 ; k<arrlen-1 -i;k++){
            if(array[k]>array[k+1]){
                let temp  = array[k];
                array[k] = array[k+1]
                array [k+1] = temp; 
            }
        }
    }
    return array;
}

let bubblesorting = random(1000);
console.log("버블 정렬 전 : ", bubblesorting);
let startTime = new Date().getTime() / 1000; //getTime 의 단위는 밀리초 => 나누기 1000을 해주면 초로 환산
console.log("버블 정렬 후 : ", bubblesort(bubblesorting));
let endTime = new Date().getTime() / 1000;
console.log(`정렬 시간 : ${endTime - startTime}`)

[2] 선택 정렬

가장 작은 항목을 찾아서 해당 항목을 배열의 현위치에 삽입

7 4 5 6 8 2 1

최솟값 1과 7을 교환 : 1 4 5 6 7 8 2

최솟값 2와 4를 교환 : 1 2 5 6 8 4 7 

최솟값 4와 5를 교환 : 1 2 4 6 8 5 7

최솟값 5와 6을 교환 : 1 2 3 5 8 6 7

최솟값 6과 8을 교환 : 1 2 3 5 6 8 7

최솟값 7과 8을 교환 : 1 2 3 5 6 7 8

//스왑하는 함수
function swap(arr,a,b){
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}



function random(n){
    let arr = new Array();
    let num;
    let temp;
    for(let i = 0;i<=n; i++){
        arr.push(i);
    }
    for(let i = 0;i <arr.length;i++){
        num = Math.floor(Math.random()*n)
        temp = arr[1];
        arr[1] = arr[num];
        arr[num] = temp;
    }
    return arr;
}

function selectSort(arr){
    const arrlen = arr.length;
    let min;

    for(let i = 0; i<arrlen;i++){
        //최소항목을 현재 위치로 설정
        min = i;

        //더작은 항목이 있는지 배열의 나머지를 확인
        for(let k = i+1;k<arrlen; k++){
            if(arr[k]<arr[min]){
                min = k;
            }
        }
        //현재위치가 최소항목 위치가 아니라면 항목 swap
        if(i!=min){
            swap(arr, i,min);
        }
    }
    return arr;
    
}

let number = random(1000);
console.log("선택 정렬 전 : ", number);
let startTime = new Date().getTime() / 1000; //getTime 의 단위는 밀리초 => 나누기 1000을 해주면 초로 환산
console.log("선택 정렬 후 : ", selectSort(number));
let endTime = new Date().getTime() / 1000;
console.log(`정렬 시간 : ${endTime - startTime}`)