정렬 알고리즘 with Javascript

용어

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입, 병합)
불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택,퀵)

 

- 버블 정렬 Bubble Sort

버블 정렬

버블정렬은 두개의 인접한 index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아가며 정렬하는 방법으로 배열의 뒷부분 부터 정렬된다.

장점

• 구현이 간단하다.
• 정렬하고자 하는 배열내에서 교환하는 방식(제자리 정렬, in place sorting)으로 추가 메모리를 필요로 하지 않는다.
• 안정 정렬(Stable Sort)이다.

단점

• 시간 복잡도가 최선, 최악, 평균 모두 O(n^2)로 비효율적이다.
• 정렬 되어있지 않는 원소가 정렬 됐을 때의 자리로 가기 위해서 교환 연산 (Swap)이 많이 발생한다.

const bubbleSort = arr => {
	for(let i=0; i<arr.length; i++) {
    	for(let j=0; j<arr.length-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    return arr
}


const arr = [1, 5, 4, 2, 3];

console.log(arr);
const sortedArr = bubbleSort(arr);
console.log(sortedArr);

 

- 선택 정렬 Selection Sort

 

선택정렬은 해당 순서에 원소를 넣을 위치는 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘으로 구현 방식은 다음의 절차를 따른다.

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체(Swap)한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

const selectionSort = arr => {
	for(let i=0; i<arr.length; i++) {
        let minIndex = i;
        
        for(let j=i+1; j<arr.length; j++) {
        	if(arr[minIndex] > arr[j]) minIndex = j;
        }
        
        if(i !== minIndex) {
        	[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }
    }
    
    return arr;
}

const arr = [1, 5, 4, 2, 3];

console.log(arr);
const sortedArr = selectionSort(arr);
console.log(sortedArr);

장점

1. 구현이 단순하다.
2. 정렬을 위한 비교 횟수는 많지만, 거품 정렬에 비해 실제 교환하는 횟수는 적기에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다.
3. 거품 정렬(Bubble Sort)과 마찬가지로 배열 안에서 교환하는 방식(제자리 정렬, in-place sort)이므로 추가 메모리가 요구되지 않습니다.

단점

1. 시간 복잡도가 O(n^2)로 비효율적입니다.
2. 불안정 정렬(unstable sort)입니다.

 

- 삽입 정렬 Insertion Sort

삽입 정렬

삽입 정렬은 기준이 되는 숫자와 그 앞에 있는 숫자를 비교하여 조건에 맞게 정렬하는 방법입니다. 0번째 인덱스는 앞쪽에 있는 숫자가 없기에 정렬의 시작은 1번째 인덱스로 합니다.

const insertionSort = arr => {
   for(let i=1; i<arr.length; i++) {
        // i - 1 까지는 이미 정렬된 배열이므로 i - 1 부터 역순으로 루프를 돌린다.
        // j 가 0 이상이면서 currentValue 보다 arr[j](정렬된 배열에 있는 값, 즉 좌측배열)이 크면 arr[j]를 arr[j+1] 이동(복사)
        let cursor = arr[i];
        let j = i-1;
        for(; j > -1 && arr[j] > cursor; j--) {
            arr[j+1] = arr[j];
        }
    	// for loop을 빠져나오면 j가 1 더 줄어들기 때문에 j + 1
        arr[j+1] = cursor;
	}
    
    return arr;
}

const arr = [1, 5, 4, 2, 3];

console.log(arr);
const sortedArr = insertionSort(arr);
console.log(sortedArr);

장점

1. 구현이 간단하다.
2. 대부분 원소들이 이미 정렬 되어있다면, 효율적일 수 있다.
3. 정렬하고자 하는 배열에서 교환하는 방식으로 추가 메모리가 요구되지 않는다. (=제자리 정렬, in-place sort)
4. 안정 정렬(Stable Sort)이다.
5. Selection Sort나 Bubble Sort와 비교해 상대적으로 빠르다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)로 비효율적이다.
• Selection, Bubble sort와 마찬가지로 배열의 길이가 길면 길수록 비효율적이다.

 

퀵정렬 Quick Sort

퀵 정렬

퀵 정렬은 비교에 기준이 되는 특정한 값(Pivot)을 기준으로 해당 값 보다 큰 숫자와 작은 숫자를 교환하면서 정렬을 수행합니다. 보통 가장 앞에 있는 값을 피봇으로 선택합니다.

불안정 정렬(unstable sort)이고 O(nlogn)의 시간 복잡도를 갖는다. 그렇다 하더라도 이미 정렬되어 있는 경우라면 삽입 정렬이 O(n)의 시간 복잡도를 갖기 때문에 항상 퀵정렬이 빠른건 아니다.

동작

1. 배열을 왼쪽에서 오른쪽으로 순회하면서 Pivot보다 큰 수를 찾습니다.
2. 배열을 오른쪽에서 왼쪽으로 순회하면서 Pivot보다 작은 수를 찾습니다.
3. 1의 결과와 2의 결과를 서로 Swap합니다.

const quickSort = (arr, start=0, end=arr.length-1) => {
    const pivot = start;
    let left = start+1;
    let right = end;
    
	if(left >= right) return;
    
    while(left <= right) {
    	while(arr[left]<=arr[pivot]) left++;
        while(arr[right]>arr[pivot]) right--;
        
        if(left < right) [arr[left], arr[right]] = [arr[right], arr[left]];
        else [arr[pivot], arr[right]] = [arr[right], arr[pivot]];
    }
    
    quickSort(arr, start, right-1);
    quickSort(arr, right+1, end);
}

const arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];

quickSort(arr);
console.log(arr);

 

병합정렬 Merge Sort

큰 문제를 작게 쪼개면서 해결해 나가는 방식으로 시간 복잡도는 퀵 정렬과 마찬가지로 O(nlogn)이지만 퀵 정렬과 달리 안정 정렬이다(stable sort). 다른 정렬 알고리즘과 달리 swap이 일어나지 않습니다.

병합 정렬

main array 와 sub array로 분리하여 sort하고 다시 합치는 divide && conquer 전략이다.

• mergeSort(arr): 반으로 나누어 주는 함수
• merge(left,right): 반으로 나누어준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수
  
  

const mergeSort = (arr) => {
    
    if(arr.length < 2) return arr;
    const mid = Math.ceil(arr.length / 2);
    
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
    const arr = [];
    while(left.length && right.length) {
    	if(left[0] < right[0]) {
        	arr.push(left.shift());
        } else {
        	arr.push(right.shift());
        }
    }
    return [...arr, ...left, ...right];
}

const arr = [7, 22, 5, 11, 32, 120, 68, 70];

const sorted = mergeSort(arr);
console.log(sorted);