[알고리즘] 정렬

선택정렬

선택 정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법이다.

앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다.

시간 복잡도 O(N^2)으로 비효율적인 정렬 알고리즘 중 하나다.

🌈 동작방식
1. 각 단계에서 가장 작은 원소를 선택한다.
2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치 를 교체한다.

function selectionSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    // 최솟값을 i번째 원소와 교환
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  
  return arr;
}

버블 정렬

단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경한다.

서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름이다.

시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘 중 하나다.

🌻 동작 방식
1.한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.
따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외한다.
2.각 단계를 거칠 떄 마다 가장 큰 값을 하나씩 확실하게 결정하는 것으로 이해할 수 있다.

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

삽입 정렬

삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다.

매 단계에서 현재 처리 중인 원소가 삽입될 위치를 찾기 위해 약 N번의 연산이 필요하다

결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

🌻 동작방식
1.각 단계에서 현재 원소가 삽입될 위치를 찾는다.
2.적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      // 인덱스 j부터 1까지 1씩 감소하며 반복
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      } else {
        //자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        break;
      }
    }
  }
  return arr;
}
console.log(insertSort([1, 3, 5, 6, 4]));

병합정렬

병합 정렬은 전형적인 분할 정복 (divide and conquer) 알고리즘이다.

1. 분할 : 큰 문제를 작은 부분 문제로 분할한다.
2. 정복 : 작은 부분 문제를 각각 해결한다.
3. 조합 : 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다.

분할 정복의 단점

일반적으로 재귀 함수를 사용한다는 점에서 함수 호출 횟수가 많이 발생한다.

이는 오버헤드로 이어진다.

병합 정렬의 특징

시간 복잡도 O(NlogN)을 보장하는 빠른 정렬 알고리즘 중 하나이다.

🌻 동작방식 1. 분할(divide): 정렬할 배열(큰 문제)을 같은 크기의 부분 배열 (작은 문제) 2개로 분할한다. 2.정복(conquer): 부분 배열을 정렬한다. (작은 문제를 해결한다.) 3. 조합(combine): 정렬된 부분 배열을 하나의 배열로 다시 병합한다.

분할 : 분할 작업은 단순히 배열의 크기를 절반으로 쪼개는 것이다.

정복 : 두 개의 부분 배열을 “정렬된 하나의 배열”로 만든다.

병합 정렬의 동작 방식 - 정복 (conquer)

• 각 부분 배열은 이미 정렬된 상태로 본다.
• 각 부분 배열에 대하여 첫쨰 원소부터 시작하여 하나씩 확인한다.
• 총 원소의 개수가 N개일 떄 ,O(N)의 시간 복잡도가 요구된다.

장점 : 최악의 경우에도 O(NlogN)을 보장할 수 있다는 점에서서 효율적이다.

단점 : 일반적인 경우 , 정복(conquer) 과정에서 임시 배열이 필요하다.`

//병합 수행 함수
function merge(arr, left, mid, right) {
  let i = left;
  let j = mid + 1;
  let k = left; // 결과 배열의 인덱스
  while (i <= mid && k <= right) {
    if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
    else sorted[k++] = arr[j++];
  }

  //왼쪽 배열에 대한 처리가 다 끝난 경우
  if (i > mid) {
    for (; j <= right; j++) sorted[k++] = arr[j];
  } else {
    for (; i <= mid; i++) sorted[k++] = arr[i];
  }

  for (let x = left; x <= right; x++) {
    arr[x] = sorted[x];
  }
}

function mergeSort(arr, left, right) {
  //원소가 1개인 경우, 해당 배열은 정렬이 된 상태로 이해 가능
  if (left < right) {
    //원소가 2개 이상이라면
    let mid = parseInt((left + right) / 2); //2개의 부분 배열로 분할
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}