[알고리즘] 정렬(버블, 삽입, 선택, 합병, 퀵, 기수)

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 최대한 간결하고 효율적이도록 만들었으며, 주어진 코드보다 좋은 코드일 것이라 생각한다!

💡 정렬별 시간·공간복잡도 정리

Algorithm	Big-O (상한)	Big-θ (평균)	Big-Ω (하한)	공간 복잡도
버블 정렬	O(n^2)	θ(n^2)	Ω(n)	O(1)
삽입 정렬	O(n^2)	θ(n^2)	Ω(n)	O(1)
선택 정렬	O(n^2)	θ(n^2)	Ω(n^2)	O(1)
합병 정렬	O(n log n)	θ(n log n)	Ω(n log n)	O(n)
퀵 정렬	O(n^2)	θ(n log n)	Ω(n log n)	O(log n)
기수 정렬	O(nk)	θ(nk)	Ω(nk)	O(n+k)

📌버블 정렬 (Bubble Sort)

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식

중첩 루프를 돌며, n개의 값이 주어졌을 때 루프가 n-1번, n-2번 반복되므로 (n-1)*(n-2) = n^2 -3n +2번의 비교·교환이 필요함

시간복잡도

O(n^2) : 최악의 경우 n^2 -3n +2번 모두 진행
Ω(n) : (최적화 설정 & 정렬된 경우) n-1번만 비교

구현

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

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

최적화 추가 : 순회 중, 교환이 발생하지 않았다면 과정을 끝냄

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort(arr) {
    let noSwap;
    for(let i = arr.length; i > 0 ; i --) {
        let noSwap = true;
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
                noSwap = false; // swap 발생 시, false로 변경
            }
        }
        if(noSwap) break;
    }
    return arr;
}

📌삽입 정렬 (Insertion Sort)

두 번째 자료부터 시작하여 앞의 자료들과 비교해 삽입할 위치를 지정한 후, 자료를 뒤로 옮기고 삽입되는 과정을 반복한 정렬

시간복잡도

O(n^2)
Ω(n) : 이미 정렬된 경우

구현

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currentValue = arr[i]; // 현재 비교할 값 저장 (arr가 계속 바뀌기 때문에 저장해야함)
        for (let j = i - 1; j >= 0 && arr[j] > currentValue; j--) { // 앞에 큰 값 있다면
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 이전 값, 현재 값 변경
        }
    }
    return arr;
}

📌선택 정렬 (Selection Sort)

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식

시간복잡도

O(n^2) : n + (n-1) + (n-2) + … = n(n-1)/2
Ω(n^2) : 정렬 여부 상관없이 모두 실행

구현

function selectionSort(arr) {

    for(let i = 0; i < arr.length; i++) {
        let lowest= i; // 최소값 설정
        for(let j = i+1; j < arr.length; j++) {
            if(arr[j] < arr[lowest]) lowest = j; // 최소값 업데이트
        }
                // 만약 최소값에 변동이 있다면 바꿔주기
        if(i !== lowest) [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }

    return arr;
}

📌합병 정렬 (Merge Sort)

배열을 요소가 하나가 될 때까지 분할 → 맨 앞 값을 하나씩 비교해 정렬하면서 합병 → 반복

시간복잡도

O(n log n) : 분할하면서 logn, 비교하면서 n
Ω(n log n)

구현

정렬
맨 앞부터 시작해서 작은 값은 result에 넣고, 포인터를 이동해가면서 비교 → 한 배열이 모두 result에 들어갔다면 나머지 배열의 남은 값 모두 넣기
합병
재귀를 이용해서 끝까지 나눴다가 합병

// 정렬 함수
function merge(arr1, arr2) {
    let p1 = 0; // arr1의 포인터
    let p2 = 0; // arr2의 포인터
    let result = [];

    while(p1 < arr1.length && p2 < arr2.length) {
        if(arr1[p1] < arr2[p2]) { // 값 비교해서 작은 값 result에 넣기
            result.push(arr1[p1]);
            p1++;
        }
        else {
            result.push(arr2[p2]);
            p2++;
        }
    }

    // 남은 배열의 값이 있다면, 나머지 다 넣기
    if(p1 < arr1.length) result.push(...arr1.slice(p1));
    else if(p2 < arr2.length) result.push(...arr2.slice(p2));

    return result;
}

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);
}

📌퀵 정렬 (Quick Sort)

피벗값(파티션) 하나를 설정해서 이보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮김 → 피벗을 다시 설정 → 반복

피벗 설정 : 편의상 맨 첫 번째 인덱스로 설정

시간복잡도

O(n^2) : 정렬된 상태에서 맨 앞 값이나 맨 뒤 값을 피벗으로 선택하면 n번 피벗이 설정되고, 매번 n번 비교되니 n^2의 시간이 들어감 → 이를 방지하기 위해서 피벗을 중간값이나 무작위로 설정해야함
Ω(n log n) : 피벗이 작은 값은 왼쪽, 큰 값은 오른쪽에 놓고 중앙에 위치하면서, 배열이 분할되고, 재귀 logn, 비교하면서 n

구현

💡 추가 공간없이 배열 그 자체를 수정해나갈 것

피벗값(파티션) 하나를 설정
피벗과 다른 값들의 크기를 비교 → 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮김 (피벗을 중앙으로 옮김)
1. 포인터 설정 = 1
2. 피벗의 다음 값부터 피벗과 비교
3. 피벗 > 값 ⇒ 포인터의 값과 해당 값을 바꾸고 포인터+1
4. 피벗 < 값 ⇒ 그냥 놔둠
5. 맨 끝까지 비교했다면, 최종적인 포인터의 값과 피벗 교체

피벗의 왼쪽, 오른쪽 부분에 재귀함수 호출
반복하며 범위가 요소 하나가 될 때까지 비교되다가, 최종 배열 반환

// array의 두 값을 교환하는 swap 함수
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

// -----------------------------------------------
// pivot의 알맞은 위치인덱스를 반환하는 함수
function pivot(arr, start = 0, end = arr.length-1) { 

    let pivot = arr[start]; // arr[0]을 피벗으로 설정
    let swapIdx = start; // 업데이트 될 반환값

    for(let i = start + 1; i <= end; i++) { // 피벗 다음 위치부터 시작
        if(pivot > arr[i]) { // 만약 피벗보다 작은 값 발견했다면
            swapIdx ++; // 위치를 하나 뒤로 옮기고
            swap(arr, i, swapIdx); // 둘이 바꿈
        }
    }

    swap(arr, start, swapIdx); // 피벗과 마지막으로 바꿨던 값이랑 swap 
    return swapIdx; // 피벗이 최종적으로 찾아간 위치 반환
}

// 피벗을 사용해 최종적으로 배열을 정렬하는 함수
function quickSort(arr, left = 0, right = arr.length-1) {
    if(left < right) { // 함수를 실행하는 부분이 값 하나가 되면 실행x
        let pivotIdx = pivot(arr, left, right); // 피벗의 위치 구해서
        quickSort(arr, left, pivotIdx-1); // 그 왼쪽 부분을 다시 재귀
        quickSort(arr, pivotIdx+1, right); // 오른쪽 부분을 다시 재귀
    }
    return arr; // 최종으로 재귀를 마친 배열 반환
}

quickSort()는 재귀의 반환값으로 뭔가를 실행하는 형태가 아니기 때문에 계속 깊게 재귀되다가 마지막 함수가 호출될 때, 반환되도록 설정해줘야 한다.

📌기수 정렬 (Radix Sort)

비교 없이 수행하는 정렬 알고리즘
(다른 정렬은 배열 내의 숫자를 비교해서 O(n^2)이었고, 한 숫자와 전체를 비교해서 O(n log n)이 최선이었음)

1의 자리부터 숫자대로 분류해서 이를 순서대로 정렬하고, 그 위의 자리의 숫자대로 분류해서 정렬하고… 이를 제일 큰 자리수까지 진행함

예시

[1556, 4, 3556, 593, 408, 4386, 902, 7, 8157, 86, 9637, 29]

1️⃣ 1의 자리수에 따라 분류, 이대로 정렬 (분류하면서 정렬은 x)

2️⃣ 위에서 정렬된 순서에 맞춰 2의 자리수에 따라 분류, 다시 넣기

3️⃣ 3의 자리, 4의 자리까지 반복하면 정렬 완료

시간 복잡도

n - 정렬할 항목 수, 정수의 수 / k - 수의 길이

O(nk) : 가장 긴 길이만큼 숫자들을 분류하므로
Ω(nk)
공간복잡도 : O(n+k)

구현

// 숫자의 i 인덱스의 숫자 알아내는 함수
function getDigit(num, i) {
    return Math.floor(num / Math.pow(10, i)) % 10;
}

// 숫자의 자릿수를 알아내는 함수
function getDigitCnt(num) {
    if(num === 0) return 1;
    return Math.floor(Math.log10(num)) + 1;
}

// 숫자의 가장 큰 자릿수를 알아내는 함수
function getMaxDigitCnt(nums) {
    let maxDigits = 0;
    for(let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, getDigitCnt(nums[i]));
    }
    return maxDigits;
}

// 본격 기수정렬
function radixSort(arr) {
    let maxDigits = getMaxDigitCnt(arr); // 가장 큰 자릿수 찾기

    for(let i = 0; i < maxDigits; i++) {
        let bucket = Array.from({length: 10}, i => []) // 자릿수의 숫자마다 담을 버킷 생성
        for(let j = 0; j < arr.length; j++) {
            let num = arr[j];
            bucket[getDigit(num, i)].push(num); // 버킷의 인덱스로 분류
        }
        arr = bucket.flatMap(v => v); // 버킷을 통합해서 arr로 만듬
    }

    return arr;
}

[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) - javascript (0)	2023.01.28
[알고리즘] BFS(넓이 우선 탐색) & DFS(깊이 우선 탐색) - javascript (0)	2023.01.18
[알고리즘] 재귀 문제 풀이 - javascript (0)	2022.08.02
[알고리즘] javascript 문제해결 패턴 - Sliding Window (기준점 간 이동) (0)	2022.07.27
[알고리즘] javascript 문제해결 패턴 - Multiple Pointers (다중 포인터) (0)	2022.07.26

성장일기