정렬과 Tim sort의 인과관계

1. 버블 정렬(bubble sort)

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 요소를 비교하여 교환하며 정렬한다.
• 이미 정렬이 되어 있는 경우(최고 케이스) : O(n)
• 정렬이 안되어 있고 요소의 개수가 많은 경우(최악 케이스) : O(n^2)

const numbers = [7, 4, 5, 1, 3];

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

bubbleSort(numbers); // [1, 3, 4, 5, 7]

 

2. 삽입 정렬(insertion sort)

• 맨 앞 요소부터 차례대로 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘
• 매 순서마다 해당 요소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
• 이미 정렬이 되어 있는 경우(최고 케이스) : O(n)
• 정렬이 안되어 있고 요소의 개수가 많은 경우(최악 케이스) : O(n^2)

const numbers = [8, 5, 6, 2, 4];

function insertionSort(arr) {
    for(let i = 1 ; i < arr.length ; i++) {
        let currentItem = arr[i];
        let j;
        
        for(j = i - 1 ; j >= 0 && arr[j] > currentItem ; j--) {
            arr[j+1] = arr[j];
        }
        
        arr[j+1] = currentItem;
    }
    console.log(arr);
}

insertionSort(numbers); // [2, 4, 5, 6, 8]

 

3. 힙 정렬(heap sort)

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 알고리즘
• 내림차순 정렬을 위해서는 최소 힙을 구성하고, 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.
• 루트 노드(최상위 노드)를 가장 마지막 노드와 교환한 후 힙 크기를 줄이는 방식으로 정렬을 수행한다.
• 힙 생성 알고리즘 후 힙 정렬을 실행한다.
• 힙 정렬 알고리즘은 항상 O(nlogn)을 보장한다.

let data = [7, 6, 5, 8, 3, 5, 9, 1, 6];

function main() {
    data = heapSort(data);
    
    console.log(data);
}

function heapSort(arr) {
    for(let i = arr.length - 1 ; i >= 0 ; i--) {
        arr = heapify(arr, i);

        if(arr[0] > arr[i]) {
            let temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
        }
    }
    return arr;
}

function heapify(arr, lastIndex) {
    let index = parseInt(lastIndex / 2) - 1;
    let temp = 0;

    while(index >= 0) {
        const left = arr[index * 2 + 1];
        const right = arr[index * 2 + 2];

        if(left >= right && arr[index] < left) {
            temp = arr[index];
            arr[index * 2 + 1] = temp;
            arr[index] = left;
        }

        if(right > left && arr[index] < right) {
            temp = arr[index];
            arr[index * 2 + 2] = temp;
            arr[index] = right;
        }
        index--;
    }

    return arr;
}

main(); // [1, 3, 5, 5, 6, 6, 7, 8, 9]

 

4. 병합 정렬(merge sort)

• 하나를 두 개로 분할한 뒤 각자 계산하고 나중에 합치는 정렬
• 항상 반으로 나누는 특징이 있는데 이는 크기를 logn이 될 수 있도록 만들어준다.
• 정렬 자체에 필요한 수행시간이 n이므로 시간복잡도는 O(n * logn)
• 합칠때 배열을 새로 만들어줘야 한다.

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

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  
  const boundary = Math.ceil(arr.length / 2);
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);

  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 6, 5, 8, 3, 5, 9, 1];
const result = mergeSort(arr);

console.log(result); // [1, 3, 5, 5, 6, 7, 8, 9]

 

5. 퀵 정렬(quick sort)

• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.
• 퀵 정렬은 매우 빠른 속도로 정렬할 수 있지만 불안정한 정렬이다.
• 대표적인 분할 정복 알고리즘으로 평균 속도가 O(nlogn)을 보장한다.
• 이미 정렬이 되어 있고 요소의 개수가 많은 경우(최악 케이스) : O(n^2)

let data = [7, 6, 5, 8, 3, 5, 9, 1, 6];

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

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

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

    const leftSorted = quickSort(left);
    const rightSorted = quickSort(right);

    return [...leftSorted, pivot, ...rightSorted];
};

quickSort(data); // [1, 3, 5, 5, 6, 6, 7, 8, 9]

 

6. 팀 정렬(tim sort)

• 삽입 정렬(insertion sort)과 병합 정렬(merge sort)을 기반으로 둔 정렬
• 파이썬의 표준 정렬 알고리즘과 자바스크립트의 sort 메서드의 알고리즘(ES10부터)
• 최고 케이스가 O(n)이고, 최악의 케이스가 O(nlogn)으로 최적화한 정렬 알고리즘