정렬 알고리즘

여러 정렬 알고리즘을 배움으로서, 어떻게 효율적인 알고리즘을 적용할지 그리고 왜 상황마다 알고리즘을 다르게 써야하는 지 개념을 잡을 수 있습니다.

https://visualgo.net/en
참고하기 좋은 사이트, 시각화 자료가 많습니다.

선택 정렬

선택 정렬은 정렬되지 않은 목록에서 최소 요소를 반복적으로 찾아 목록의 시작 부분으로 이동하는 간단한 정렬 알고리즘입니다. 알고리즘은 처음에 비어 있는 정렬된 하위 목록과 나머지 모든 요소를 포함하는 정렬되지 않은 하위 목록의 두 하위 목록을 유지합니다.

• 빅오 : O(n^2)

장단점

장점:

• 선택 정렬은 구현과 이해가 쉽기 때문에 정렬 알고리즘을 처음 배우는 사람들에게 좋은 선택입니다.
• 선택 정렬은 작은 목록에서 잘 수행되며 일반적으로 대부분의 입력에 대해 버블 정렬보다 빠릅니다.
• 선택 정렬은 임시 변수를 저장하기 위해 일정한 양의 추가 공간만 필요하기 때문에 상대적으로 적은 양의 메모리를 사용합니다.

단점:

• 선택 정렬은 시간 복잡도가 O(n^2)이므로 큰 목록이나 데이터 세트에 비효율적입니다.
• 선택 정렬은 목록이 이미 정렬되었거나 부분적으로 정렬된 경우에도 동일한 수의 비교를 수행하므로 시간이 낭비됩니다.
• 선택 정렬은 안정적인 정렬 알고리즘이 아닙니다. 즉, 동일한 요소의 상대적인 순서를 유지하지 않습니다. 입력 목록에 중복 값이 ​​있는 개체가 포함되어 있고 원래 순서를 유지하는 것이 중요한 경우 문제가 될 수 있습니다.

수도 코드

1. 먼저, 알고리즘은 처음에 비어 있는 정렬된 하위 목록과 나머지 모든 요소를 ​​포함하는 정렬되지 않은 하위 목록의 두 하위 목록을 초기화합니다.
2. 그런 다음 알고리즘은 정렬되지 않은 하위 목록에서 가장 작은 요소를 검색하고 정렬되지 않은 하위 목록의 첫 번째 요소와 교체하여 목록의 시작 부분으로 이동합니다.
3. 정렬되지 않은 하위 목록의 첫 번째 요소는 이제 정렬된 하위 목록의 일부로 간주되므로 정렬되지 않은 하위 목록에서 제거되고 정렬된 하위 목록의 끝에 추가됩니다.
4. 알고리즘은 전체 목록이 정렬될 때까지 정렬되지 않은 하위 목록의 각 후속 요소에 대해 2단계와 3단계를 반복합니다.

코드

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

// Example usage:
let arr = [5, 3, 8, 4, 2];
console.log(selectionSort(arr)); // [2, 3, 4, 5, 8]

버블 정렬

버블 정렬은 인접한 요소의 순서가 잘못된 경우 반복적으로 교체하는 간단한 정렬 알고리즘입니다.

장단점

장점:

• 버블 정렬은 이해하고 구현하기 쉬워 정렬 알고리즘을 처음 배우는 사람들에게 좋은 선택입니다.
• 버블 정렬은 작은 데이터 세트 또는 목록에 효율적입니다.
• 버블 정렬은 동일한 요소의 상대적인 순서를 유지하는 안정적인 정렬 알고리즘입니다.

단점:

• 버블 정렬은 시간 복잡도가 O(n^2)이므로 더 큰 데이터 세트나 목록에 비효율적입니다.
• 버블 정렬은 목록이 이미 정렬되었거나 부분적으로 정렬된 경우에도 동일한 수의 비교를 수행하므로 시간이 낭비됩니다.
• 버블 정렬은 스왑을 수행하기 위해 임시 변수가 필요하기 때문에 상대적으로 많은 양의 메모리를 사용합니다.

알고리즘 동작

• 알고리즘은 목록의 시작 부분에서 시작하여 처음 두 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 서로 바꿉니다.
• 그런 다음 알고리즘은 인접한 요소의 다음 쌍으로 이동하고 필요한 경우 동일한 비교 및 ​​교환을 수행합니다. 이 프로세스는 목록 끝에 도달할 때까지 목록의 모든 인접 요소 쌍에 대해 반복됩니다.
• 이 시점에서 가장 큰 요소는 목록의 끝에 있는 것이 보장되므로 알고리즘은 목록의 처음부터 다시 프로세스를 반복하지만 이번에는 이미 정렬된 마지막 요소를 무시합니다.
• 알고리즘은 더 이상 스왑이 필요하지 않을 때까지 목록을 계속 통과하여 목록이 정렬되었음을 나타냅니다.

코드

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

// Example usage:
let arr = [5, 3, 8, 4, 2];
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

삽입 정렬

삽입 정렬은 전체 배열이 정렬될 때까지 한 번에 한 요소씩 배열의 정렬된 부분을 반복적으로 구축하여 작동하는 간단한 정렬 알고리즘입니다. 배열을 반복하고 각 요소를 배열의 정렬된 부분에서 올바른 정렬된 위치에 삽입하여 이를 수행합니다.

장단점

삽입 정렬은 작은 데이터셋이나 부분적으로 정렬된 데이터셋에는 간단하고 효율적이지만
최악의 경우 시간 복잡도는 O(n^2)이므로 큰 데이터셋에는 비효율적입니다.

알고리즘 동작

• 배열의 정렬된 부분으로 첫 번째 요소부터 시작합니다.
• 각 후속 요소에 대해 배열의 정렬된 부분에 있는 각 요소와 비교하여 올바른 위치를 찾을 때까지 각 요소를 한 인덱스 위로 이동합니다.
• 배열의 정렬된 부분에서 올바른 위치에 요소를 삽입합니다.
• 전체 배열이 정렬될 때까지 반복합니다.

코드

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

// Example usage:
let arr = [5, 3, 8, 4, 2];
console.log(insertionSort(arr)); // [2, 3, 4, 5, 8]

병합 정렬

입력 배열을 더 작은 하위 배열로 나누고 이러한 하위 배열을 재귀적으로 정렬한 다음 다시 병합하여 정렬된 배열을 얻는 분할 정복 알고리즘입니다. 병합 정렬의 기본 아이디어는 각 하위 배열이 하나의 요소만 포함할 때까지 반복적으로 입력 배열을 절반으로 나눈 다음 하위 배열을 병합하여 정렬된 출력 배열을 형성하는 것입니다.

장단점

장점:

• 병합 정렬은 최악의 경우 O(n log n)의 시간 복잡도를 보장하므로 큰 입력 크기에 효율적입니다.
• 안정적인 정렬입니다. 즉, 정렬된 출력에서 ​​동일한 요소의 상대적 순서를 유지합니다.
  쉽게 병렬화할 수 있으므로 병렬 처리 응용 프로그램에 유용합니다.

단점:

• 병합 정렬은 병합 단계에서 하위 배열을 저장하기 위해 추가 메모리가 필요하므로 다른 정렬 알고리즘보다 공간 복잡성이 높습니다.
• 재귀 호출 및 병합의 오버헤드가 알고리즘의 이점보다 클 수 있으므로 작은 입력 크기에는 최선의 선택이 아닐 수 있습니다.

알고리즘 동작

• 입력 배열을 두 부분으로 나눕니다.
• 병합 정렬을 사용하여 왼쪽 및 오른쪽 절반을 재귀적으로 정렬합니다.
• 정렬된 왼쪽 및 오른쪽 절반을 다시 병합하여 정렬된 단일 배열을 형성합니다.

코드

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));
  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.concat(left, right);
}

자바스크립트에서 정렬하기