정렬 알고리즘

1. 거품 정렬 (Bubble Sort)

• 설명: 인접한 두 원소를 비교하여 서로 교환하는 방식
• 프로세스:
  1. 리스트의 첫 번째 원소부터 인접한 원소를 비교하여 필요에 따라 교환
  2. 리스트 끝까지 이동한 후, 가장 큰 원소가 마지막에 위치
  3. 리스트의 길이만큼 반복
• 시간복잡도: 최선/평균/최악 O(n^2)
• 장단점:
  • 장점: 구현이 간단, 제자리 정렬, 안정 정렬
  • 단점: 비효율적

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

 

2. 선택 정렬 (Selection Sort)

• 설명: 주어진 리스트에서 최솟값을 선택하여 맨 앞의 원소와 교환
• 프로세스:
  1. 리스트에서 최솟값 탐색
  2. 최솟값을 정렬되지 않은 리스트의 맨 앞 원소와 교환
  3. 반복
• 시간복잡도: 최선/평균/최악 O(n^2)
• 장단점:
  • 장점: 구현이 간단, 제자리 정렬 , 버블 정렬 보다 교환 적음
  • 단점: 비효율적, 불안정 정렬

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

3. 삽입 정렬 (Insertion Sort)

• 설명: 정렬되지 않은 부분의 원소를 하나씩 정렬된 부분에 삽입해가며 정렬
• 프로세스:
  1. 정렬되지 않은 부분의 첫 원소를 정렬된 부분의 적절한 위치에 삽입
  2. 반복
• 시간복잡도: 최선 O(n), 평균/최악 O(n^2)
• 장단점:
  • 장점: 대부분의 원소가 이미 정렬되어 있는 경우에 효율적, 제자리 정렬, 안정 정렬
  • 단점: 역순으로 정렬되어 있는 경우에는 매우 비효율적

function insertionSort(arr) {
    const len = arr.length;
    for (let i = 1; i < len; 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;
    }
    return arr;
}

 

4. 퀵 정렬 (Quick Sort)

• 설명: 분할 정복 방식
• 프로세스:
  1. 리스트에서 피벗을 선택
  2. 피벗을 기준으로 작은 원소는 피벗의 왼쪽으로, 큰 원소는 피벗의 오른쪽으로 분할
  3. 분할된 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행
  4. 반복
• 시간복잡도: 평균 O(n log n), 최악 O(n^2)
• 장단점:
  • 장점: 평균적으로 매우 빠름, 제자리 정렬
  • 단점: 불안정 정렬, 

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), pivot, ...quickSort(right)];
}

5. 병합 정렬 (Merge Sort)

• 설명: 리스트를 반으로 나누고 각각을 재귀적으로 정렬한 후, 정렬된 부분 리스트를 병합
• 프로세스:
  1. 리스트를 반으로 나눔
  2. 각 부분 리스트에 대해 재귀적으로 병합 정렬을 호출
  3. 정렬된 부분 리스트들을 병합
• 시간복잡도: 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 = [];
    
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    
    return [...result, ...left, ...right];
}

6. 힙 정렬 (Heap Sort)

• 설명: 힙 자료구조를 이용
• 프로세스:
  1. 주어진 리스트를 최대 힙으로 만듬
  2. 힙에서 최댓값을 추출하여 리스트의 가장 끝에 위치한 값과 교환
  3. 힙 크기를 줄이고(추출한 최댓값), 교환된 원소를 기준으로 다시 힙을 구성
  4. 반복
• 시간복잡도: O(n log n)
• 장단점:
  • 장점: 평균적으로 빠름, 제자리 정렬
  • 단점: 불안정 정렬

function heapSort(arr) {
    // 배열을 힙으로 변환
    buildMaxHeap(arr);

    // 힙으로부터 원소를 하나씩 추출하여 정렬
    for (let i = arr.length - 1; i > 0; i--) {
        // 최대값과 현재 값을 교환
        [arr[0], arr[i]] = [arr[i], arr[0]];

        // 힙 속성을 유지하기 위해 최대 힙 재구성
        maxHeapify(arr, 0, i);
    }

    return arr;
}

// 최대 힙 생성 함수
function buildMaxHeap(arr) {
    const n = arr.length;
    for (let i = Math.floor(n / 2); i >= 0; i--) {
        maxHeapify(arr, i, n);
    }
}

// 최대 힙 속성 유지 함수
function maxHeapify(arr, i, size) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

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

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

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        maxHeapify(arr, largest, size);
    }
}

7. 기수 정렬 (Radix Sort)

• 설명: 자리수 기준으로 비교 없이 정렬
• 프로세스:
  1. 가장 큰 수를 찾고, 이를 기준으로 순회할 최대 자릿수를 결정
  2. 가장 낮은 자릿수부터 시작하여, 각 숫자를 현재 자릿수에 해당하는 숫자에 따라 0~9의 버킷에 분류
  3. 모든 버킷의 내용을 순서대로 배열에 다시 병합
  4. 반복
• 시간복잡도: O(d * (n + k)),  d: 숫자의 최대 자릿수, n: 리스트의 크기, k: 숫자의 범위(0~9)
• 장단점:
  • 장점: 안정 정렬, 비교 연산을 하지 않기 때문에 일반적인 비교 정렬 알고리즘보다 빠름
  • 단점: 추가적인 메모리 공간이 필요, 숫자의 범위가 매우 큰 경우에는비효율적.

function radixSort(arr) {
  const maxNum = Math.max(...arr) * 10;
  let divisor = 10;
  while (divisor < maxNum) {
    // 버킷 초기화
    let buckets = [...Array(10)].map(() => []);
    // 배열의 각 요소를 적절한 버킷에 배치
    arr.forEach((num) => {
      buckets[Math.floor((num % divisor) / (divisor / 10))].push(num);
    });
    // 버킷의 내용을 배열에 병합
    arr = buckets.flat();
    // 다음 자릿수로 이동
    divisor *= 10;
  }
  return arr;
}

 

 

 

8. 계수 정렬 (Counting Sort)

• 설명: 각 정수의 등장 횟수를 세어 정렬
• 프로세스:
  1. 주어진 리스트에서 최솟값과 최댓값을 구함
  2. 최솟값과 최댓값의 범위만큼 카운팅 배열을 초기화
  3. 주어진 리스트를 순회하면서 각 원소의 등장 횟수를 카운팅 배열에 기록
  4. 카운팅 배열을 이용하여 정렬된 리스트를 생성
• 시간복잡도: O(n + k), n: 리스트의 크기, k: 정수의 범위
• 장단점:
  • 장점: 정수 리스트에 대해서는 빠른 성능을 보이며 안정적
  • 단점: 정수의 범위가 큰 경우에는 메모리 사용이 매우 크게 증가

function countingSort(arr) {
    // 배열에서 최소값과 최대값 찾기
    const max = Math.max(...arr);
    const min = Math.min(...arr);

    // 최소값을 고려하여 발생 횟수를 저장할 배열 초기화
    const range = max - min + 1;
    const count = new Array(range).fill(0);

    // 각 요소의 발생 횟수 계산
    arr.forEach(element => {
        count[element - min]++;
    });

    // 정렬된 배열을 만들기 위한 인덱스
    let index = 0;

    // 정렬된 배열 만들기
    for (let i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }

    return arr;
}