[Javascript] Bubble Sort, Selection Sort, Insertion Sort (버블/선택/삽입 정렬)

버블 정렬과 선택 정렬, 삽입 정렬은 은 가장 간단한 정렬방법들이다.

모두 O(N^2)의 시간복잡도를 갖는다.

 

버블 정렬

배열 처음부터 두 요소씩 선택하여 뒷 요소가 더 작으면 자리를 바꿔나가는 방식이다.

    function bubble(arr){
        // 배열을 처음부터 두 요소씩 선택하여 뒷 요소가 더 작으면 자리를 바꿔나간다.
        // 다시 처음부터... n^2번 실행
        const len = arr.length-1;
        let temp, i, j;
        for(i=0; i<len; i++){
            for(j=i+1; j<len; j++){
                console.log(i,j);
                if(arr[i] > arr[j]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    console.log(i, j,'자리바꿈', arr)
                }
            }
            console.log('===');
        }
        return arr;
    }

 

 

선택 정렬

1. 배열을 처음부터 탐색하여 가장 작은 수를 찾아 가장 앞 요소와 자리를 바꾼다.

[3, 4, 2, 1] => [1, 4, 2, 3]

2. 남은 요소들을 탐색하여 가장 작은 수를 찾아 두번째 요소와 자리를 바꾼다.

[1, 4, 2, 3] => [1, 2, 4, 3]

3. 반복

    function selection(arr) {
        // 배열을 처음부터 탐색하여 가장 작은 수를 찾는다
        // 배열의 가장 앞의 요소와 자리를 바꾼다.
        // 남은 배열을 탐색하여 가장 작은 수를 찾아 앞 요소와 자리를 바꾼다
        const len = arr.length;
        let minIndex, i, j;
        for (i = 0; i < len; i++) {
            minIndex = i;
            for (j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
                console.log(i, j, minIndex, arr[minIndex])
            }
            console.log('===');
            const temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }

 

 

삽입 정렬

첫번째 데이터(피벗 데이터)가 이미 정렬된 상태라고 가정하고,

다음 데이터부터 앞 데이터의 앞쪽 또는 뒷쪽 어디로 가야할지 판단한다.

앞쪽으로 한칸 더 이동할지도 이어서 판단한다.

 

[2, 4, 3, 1] 2는 이미 정렬된 상태라고 가정하고, 다음 요소인 4가 2의 앞 뒤 어디로 가야할지 판단

[2, 4, 3, 1] 2보다 크므로 옮기지 않는다.

[2, 4, 3, 1] 3은 4보다 작으므로 앞으로 한칸 옮긴다.

[2, 3, 4, 1] 3은 2보다 크므로 옮기지 않는다.

[2, 3, 4, 1] 1은 4보다 작으므로 앞으로 한칸 옮긴다.

[2, 3, 1, 4] 1은 3보다 작으므로 앞으로 한칸 옮긴다.

[2, 1, 3, 4] 1은 2보다 작으므로 앞으로 한칸 옮긴다.

[1, 2, 3, 4] 정렬 완료

    function insertion(arr){
        // 첫번째 데이터(피벗 데이터)가 이미 정렬된 상태라고 가정하고,
        // 다음 데이터부터 앞 데이터의 앞쪽 또는 뒷쪽 어디로 가야할지 판단한다.
        // 앞쪽으로 이동했다면, 이동한 자리에서 앞 데이터의 앞쪽으로 가야할지도 판단
        const len = arr.length;
        let i, j;
        for(i=1; i<len; i++){
            let temp = arr[i]; // 정렬할 숫자 선택 7
            console.log(temp+' 비교합니다')
            for(j=i-1; j>-1 && temp < arr[j]; j--){
                console.log(i, j);
                arr[j+1] = arr[j];
                console.log(arr);
            }
            arr[j+1] = temp;
            console.log('===');
        }
        return arr;
    }