정렬 알고리즘

정렬 알고리즘은 데이터 리스트를 특정 순서로 재배열하는 알고리즘
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다

(1) 버블정렬

• 버블정렬은 가장 단순한 정렬 알고리즘 중 하나로, 리스트를 반복적으로 순회하며 인접한 두 요소를 비교하고, 필요에 따라 위치를 교환하면서 정렬
• 한 번의 순회가 끝나면 가장 큰(혹은 작은)요소가 리스트의 끝에 위치
• 이 과정을 리스트가 정렬될 때까지 반복

사용되는 예시

• 정렬 알고리즘의 기본 원리를 이해하는 데 유용
• 데이터셋이 매우 작을 때 구현이 간단하여 사용

시간복잡도

• 최악 : O(n²)
• 최선 : O(n)
• 평균 : O(n²)

예시 코드

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]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
  return arr;
}

(2) 삽입정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

사용되는 예시

• 소규모 배열이나, 리스트에서 사용
• 입력되는 데이터가 연속적으로 도착하는 경우, 삽입 정렬을 사용하여 실시간으로 정렬

시간복잡도

• 최악 : O(n²)
• 최선 : O(n)
• 평균 : O(n²)

예시코드

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

let arr = [64, 34, 25, 12, 22, 11, 90];
insertionSort(arr);
console.log("Sorted array:", arr);

(3) 선택정렬

• 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞에 위치시키고, 다음으로 작은 값을 찾아 두 번째에 위치시키는 과정을 반복하여 정렬하는 알고리즘
• 간단하고 이해하기도 쉽지만, 시간복잡도가 높아 많은 데이터를 정렬시킬시에 성능이 떨어짐

사용되는 예시

• 작은 데이터셋에서 간단하게 구현 가능
• 선택 정렬은 추가적인 메모리 사용이 적기 때문에 메모리 사용이 제한적인 환경에서 사용

시간복잡도

최악 : O(n²)
최선 : O(n²)
평균 : O(n²)

예시코드

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

const unsortedArr = [3, 1, 6, 2, 9, 0];
const sortedArr = selectionSort(unsortedArr);
console.log(sortedArr); 

(4) 퀵 정렬

• 퀵 정렬은 기준점 Pivot 을 정하고 배열의 한 쪽으로는 Pivot 보다 작은 값을, 다른 쪽으로는 Pivot 보다 큰 값을 정렬해 나가는 알고리즘

사용되는 예시

• 큰 데이터셋을 정렬할 때, 특히 메모리 내에서의 정렬이 필요할 때 사용
• 자주 사용되는 Javascript의 'Array.prototyep.sort()'메서드는 내부적으로 퀵 정렬을 사용함

시간복잡도

최악 : O(n²) (최악의 경우는 피벗이 가장 크거나 작은 요소일 때)
최선 : O(n log n) (리스트가 균등하게 분할되는 경우)
평균 : O(n log n)

예시코드

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

function quickSort(arr, low, high) {
    if (low < high) {
        let pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

let arr = [64, 34, 25, 12, 22, 11, 90];
quickSort(arr, 0, arr.length - 1);
console.log("Sorted array:", arr);

(5) 병합 정렬

• 리스트를 절반으로 나눈 후 각각을 재귀적으로 정렬한 다음, 정렬된 리스트들을 병합하여 최종적으로 정렬된 리스트를 만드는 알고리즘

사용되는 예시

• 대량의 데이터가 메모리의 용량을 초과할 때 사용, 예를 들어 대형 파일을 정렬하는 작업에서 병합 정렬이 효과적
• 데이터베이스에서의 쿼리 결과를 정렬할 때 사용되기도 함

시간 복잡도

최악 : O(n log n)
최선 : O(n log n)
평균 : 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 i = 0, j = 0;

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

    return result.concat(left.slice(i)).concat(right.slice(j));
}

let arr = [64, 34, 25, 12, 22, 11, 90];
arr = mergeSort(arr);
console.log("Sorted array:", arr);

(6) 힙 정렬

• 힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘
• 최대 힙이나 최소 힙을 구성하여, 힙의 루트 요소가 최대값 혹은 최소값이 되도록 함
• 최대값 혹은 최소값을 제거하고, 나머지 요소로 힙을 재구성하는 과정을 반복하여 리스트를 정렬

사용되는 예시

• 힙 정렬은 우선순위 큐의 구현에 사용됨, 예를 들어 다익스트라의 최단 경로 알고맂므에서 힙을 사용하여 최소 비용의 노드를 효율적을 선택
• 메모리 제한이 엄격한 환경에서 사용

시간 복잡도

최악 : O(n log n)
최선 : O(n log n)
평균 : O(n log n)

예시 코드

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function heapSort(arr) {
    let n = arr.length;

    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
}

let arr = [64, 34, 25, 12, 22, 11, 90];
heapSort(arr);
console.log("Sorted array:", arr);