TIL-2024.02.29 - 알고리즘 - 정렬 알고리즘

------- 정렬 알고리즘 

설명: 데이터를 특정한 기준에 따라 정렬하는 알고리즘

종류: 

1. 버블 정렬 (Bubble Sort) 
2. 선택 정렬 (Selection Sort) 
3. 삽입 정렬 (Insertion Sort) 
4. 퀵 정렬 (Quick Sort) 
5. 합병 정렬 (Merge Sort)

 

버블 정렬 (Bubble Sort):

• 인접한 두 원소를 비교하여 순서대로 정렬하는 방식. 
• 시간 복잡도는 O(n^2)로 비효율적인 알고리즘, 구현이 간단. 
• 작은 데이터나 교환 횟수가 적은 경우에 적합.
  
  
  

예제: 

 

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

let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

 

 

선택 정렬 (Selection Sort):

• 주어진 리스트에서 최솟값을 선택하여 정렬된 리스트에 추가하는 방식.
• 시간 복잡도는 O(n^2)으로 비효율적, 버블 정렬보다는 성능이 조금 나음.
• 구현이 간단하고 작은 리스트에서 사용하기에 적합.
  
  
  

예제:

 

function selectionSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        let min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min !== i) {
            let temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    return arr;
}

let arr = [64, 25, 12, 22, 11];
console.log(selectionSort(arr)); // [11, 12, 22, 25, 64]

 

 

 

삽입 정렬 (Insertion Sort):

• 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입.
• 시간 복잡도는 평균적으로 O(n^2), 데이터가 이미 거의 정렬된 경우에는 효율적.
• 데이터가 적은 경우나 거의 정렬된 경우에 유용.

예제:

 

function insertionSort(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        let current = arr[i];
        let j = i - 1;
        while ((j > -1) && (current < arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
    return arr;
}

let arr = [12, 11, 13, 5, 6];
console.log(insertionSort(arr)); // [5, 6, 11, 12, 13]

 

 

 

 

퀵 정렬 (Quick Sort):

• 분할 정복(divide and conquer) 알고리즘
• 기준 원소(pivot)를 선택하고, 기준 원소보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치.
• 재귀적으로 이 과정을 반복하여 정렬을 수행.
• 평균적으로 시간 복잡도는 O(n log n)이며, 효율적인 정렬 알고리즘 중 하나.
  
  
  

예제:

 

function quickSort(arr) {
    if (arr.length <= 1) return arr;

    let pivot = arr[0];
    let left = [];
    let right = [];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(quickSort(arr)); // [3, 9, 10, 27, 38, 43, 82]






주어진 배열: [38, 27, 43, 3, 9, 82, 10]

첫 번째 회차(iteration):

피벗(pivot): 38
left: [27, 3, 9, 10]
right: [43, 82]
정렬된 배열: [27, 3, 9, 10, 38, 43, 82]
두 번째 회차(iteration):

피벗(pivot): 27
left: [3, 9, 10]
right: []
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]
세 번째 회차(iteration):

피벗(pivot): 3
left: []
right: [9, 10]
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]
네 번째 회차(iteration):

피벗(pivot): 9
left: []
right: [10]
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]
다섯 번째 회차(iteration):

피벗(pivot): 10
left: []
right: []
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]
여섯 번째 회차(iteration):

피벗(pivot): 43
left: []
right: [82]
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]
일곱 번째 회차(iteration):

피벗(pivot): 82
left: []
right: []
정렬된 배열: [3, 9, 10, 27, 38, 43, 82]

 

 

 

 

합병 정렬 (Merge Sort):

• 분할 정복 알고리즘을 기반으로 하며, 리스트를 반으로 나눈 후 각각을 재귀적으로 정렬하고 합병하여 정렬된 리스트를 생성합니다.
• 시간 복잡도는 항상 O(n log n)으로 효율적입니다.
• 퀵 정렬과 달리 데이터의 분포에 영향을 받지 않으므로 안정적입니다.

예제:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]