JavaScript 정렬(Sorting) 알고리즘: 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬

1. 선택 정렬(Selection Sort)

• 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법
• 앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다.
• 시간 복잡도 O(n^2)으로 비효율적인 정렬 알고리즘
• 매 단계 마다 가장 작은값이 왼쪽으로 이동(작은 값이 결정)

function selectionSort(arr){
  for(let i=0;i<arr.length;i++){
    let minIndex=i // 가장 작은 원소의 인덱스
    for(let j=i+1;j<arr.length;j++){
      if(arr[minIndex]>arr[j]){
        minIndex = j
      }
    }
    //스와프(swap)
    let temp = arr[i]
    arr[i]=arr[minIndex];
    arr[minIndex]=temp
  }
  return arr
}

2. 버블 정렬(Bubble Selection)

• 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경한다.
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름이다.
• 시간 복잡도 O(n^2)으로 비효율적인 정렬 알고리즘
• 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.
• 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정하는 것

function bubbleSort(arr){
  for(let i=arr.length-1;i>0;i--){
    for(let j=0;j<i;j++){
      if(arr[j]>arr[j+1]){ //등호를 바꿔서 내림, 오름차순 변경
        let temp = arr[j]
        arr[j]=arr[j+1]
        arr[j+1]=temp
      }
    }
  }
  return arr
}

3. 삽입 정렬(Insertion Sort)

• 각 단계에서 현재 원소가 삽입될 위치를 찾는다.
• 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.
• 삽입 정렬을 수행할 때는 처음에 첫 번째 원소는 정렬이 되어 있다고 고려한다.
• 삽입할 원소를 기준으로 왼쪽에 있는 원소들은 이미 정렬이 되어있음
• 선택 정렬과 버블 정렬 보다는 효율적이지만 시간 복잡도 O(n^2)으로 비효율적인 정렬 알고리즘

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

 

4. 병합 정렬(Merge Sort)

• 분할 정복(divide and conquer): 큰 문제를 작은 부분 문제로 분할한 후 작은 문제 해결 => 큰문제 해결
• 일반적으로 재귀 함수를 이용하여 구현한다=> 함수 호출 횟수가 많아짐 => 오버헤드
• 시간 복잡도 O(NlogN)을 보장하는 빠른 정렬 알고리즘 중 하나

function mergeSort(arr) {
  // 배열이 하나 이하의 요소를 가지고 있다면 이미 정렬된 것으로 간주합니다.
  if (arr.length <= 1) {
    return arr;
  }
  
  // 배열을 반으로 나눕니다.
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 재귀적으로 각 배열을 정렬합니다.
  const leftSorted = mergeSort(left);
  const rightSorted = mergeSort(right);
  
  // 두 배열을 병합합니다.
  return merge(leftSorted, rightSorted);
}

function merge(left, right) {
  const result = [];
  
  // 왼쪽 배열과 오른쪽 배열에서 가장 작은 요소를 찾아 결과 배열에 추가합니다.
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  
  // 아직 남아있는 요소들을 결과 배열에 추가합니다.
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  
  return result;
}