정렬 알고리즘

버블 정렬(Bubble Sort)

잘 사용되는 알고리즘이 아니다 보니 가볍게 짚어보도록 하겠다.

버블 정렬은 루프를 돌면서 해당 요소와 다음 요소를 비교하여 해당 요소가 더 크다면 교환(swap)을 한다. 이런 식으로 완전히 정렬이 될 때까지 계속 반복한다. 즉, 가장 큰 수부터 배열 끝에 정렬이 이루어진다.

function bubbleSort(arr) {
	let noSwaps;
	for (let i=arr.length; i>0; i--) {
		noSwaps = true;
		for (let j=0; j<i-1; j++) {
			if (arr[j] > arr[j+1]) {
				// SWAP!
				let temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				noSwaps = false;
			}
		}
		if(noSwaps) break;
	}
	return arr;
}
bubbleSort([37, 45, 29, 8])

버블 정렬은 정렬이 되었음에도 반복이 남았다면 계속 실행된다는 단점이 있다. 때문에 교환이 일어나지 않으면 break문을 걸어주어 루프에서 탈출시켜야 한다.

 

선택 정렬(Selection Sort)

선택 정렬은 버블정렬과는 다르게 최솟값을 찾아서 앞에서부터 정렬한다. 여기에서 버블정렬과의 차이점은 일일이 바꾸어가면서 최댓값을 정렬하는 것이 아니라 루프를 돌면서 최솟값을 기억했다가 끝에 도달했을 때 최솟값을 확정 짓고 교환한다는 점이다.

function selectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
			// j가 현재 값보다 작을 경우, 최솟값에 인덱스를 저장한다.
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            // SWAP! 교환해주기
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

selectionSort([0,2,34,22,10,19,17]);

배열의 길이만큼 반복문을 돌리는데, 가장 먼저 최솟값을 저장할 변수 만들어주고 다음 항목과 비교할 반복문을 만들어준다. 이때 비교했을 때 더 작은 값으로 갱신해 준다. 이때 값을 저장하는 것이 아닌 해당 인덱스를 저장한다. 이렇게해야 값을 교환할 수 있기 때문이다. 앞에서부터 정렬이 이루어지기 때문에 정렬이 된 위치는 제외하고 비교를 해줘야 최솟값이 잘 반영된다는 점도 기억하자!

교환된 인덱스의 다음 요소부터 시작하여 새로운 최솟값을 찾고 교환하고를 반복한다.

 

삽입 정렬(Insertion Sort) ⭐️

삽입 정렬은 한 요소를 올바른 위치에 삽입해서 배열의 요소들을 점진적으로 정렬해 간다. 때문에 새로운 요소가 추가되어 데이터를 계속 정렬해야 할 경우에 효과가 좋다.

function insertionSort(arr){
	var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
		// j가 0이상이고 현재 값보다 클 때 거꾸로 수행할 반복문
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2,1,9,76,4])

 

→ 버블, 선택, 삽입 정렬은 모두 O(n^2)의 복잡도를 지녔다.

 

병합 정렬(Merge Sort) ⭐️

전형적이 분할 정복(divide and conquer) 알고리즘이다. 

분할 정복(divide and conquer)
1. 분할(divide): 큰 문제를 작은 부분 문제로 분할한다.
2. 정복(conquer): 작은 부분 문제를 각각 해결한다.
3. 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다.

→ 일반적으로 재귀 함수를 이용하여 구현한다. 더 이상 쪼갤 수 없는 크기가 될 때까지 분할하기 위해서이다. 그러나 함수 호출 횟수가 많이 발생한다는 측면에서 오버헤드(overhead)로 이어진다.

그림에서 정복과 조합 단계에서는 정렬이 된 각 부분 배열을 비교하여 또 하나의 정렬된 조합 배열을 만들어 나아가는 방식이다.

function merge(arr1, arr2){
    let results = [];
    let i = 0;
    let j = 0;
    while(i < arr1.length && j < arr2.length){
        if(arr2[j] > arr1[i]){
            results.push(arr1[i]);
            i++;
        } else {
            results.push(arr2[j])
            j++;
        }
    }
    while(i < arr1.length) {
        results.push(arr1[i])
        i++;
    }
    while(j < arr2.length) {
        results.push(arr2[j])
        j++;
    }
    return results;
}

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

mergeSort([10,24,76,73])

 

→ 병합 정렬은 O(N log N)을 보장한다.