Sort with Javascript

1. Bubble Sort(버블 정렬)

버블 정렬은 정렬 알고리즘 중에서 가장 간단한 알고리즘 중 하나로, 인전합 두 개의 요소를 비교하며 정렬하는 방법이다.

1. 배열의 첫 번째 요소부터 마지막 요소까지 순회한다.
2. 현재 요소와 다음 인접한 요소를 비교한다.
3. 만약 현재 요소가 다음 요소보다 크다면, 두 요소의 위치를 교환한다.
4. 이렇게 하나의 반복문이 끝나면, 가장 큰 요소가 배열의 마지막으로 이동하게 된다.
5. 마지막 요소를 제외한 이전 요소들에 대해 위의 단계를 반복하여 정렬을 완료한다.

이름이 버블 정렬인 이유는 정렬 과정에서 가장 큰 요소가 배열의 뒷부분으로 "버블"처럼 이동하기 때문이다. 버블 정렬은 간단하고 이해하기 쉬운 알고리즘이지만, 비효율적인 알고리즘이기 때문에 대규모 데이터를 정렬하는 데에는 적합하지 않다. 평균 및 최악의 시간 복잡도는 O(n^2)이며, 데이터의 개수가 만을 수록 정렬 시간이 급격하게 증가한다.

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

    for (let i = 0; i < n - 1; i++) {
      // 각 반복에서 가장 큰 요소가 배열 끝으로 이동하므로, 마지막 요소는 정렬되어 있음
      // 따라서 i번째 반복에서는 마지막 i개의 요소는 정렬할 필요 없음
      for (let j = 0; j < n - 1 - i; j++) {
        // 인접한 두 요소를 비교하여 크기 순서가 올바르지 않으면 위치를 교환
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6의 배열 분할 할당(Array Destructuring Assignment)
        }
      }
    }
  }

  // 예시 사용법
  const arr = [8, 16, 88, 18, 343, 0, 100, 28, 90000, 0.5, 7, 13];
  console.log("정렬 전:", arr);

  bubbleSort(arr);

  console.log("정렬 후:", arr);

 

2. Insertion Sort(삽입 정렬)

시간 복잡도 O(n^2)를 가지는 정렬 방식으로 배열의 크기가 작거나 이미 정렬이 많이 되어있는 상태의 배열인 상태일 때 가장 효율적이다.

1. 첫 번째 요소는 이미 정렬된 상태로 간주한다.
2. 두 번째 요소부터 시작하여 정렬되지 않은 부분 배열에서 요소를 선택한다.
3. 선택한 요소를 이미 정렬된 부분 배열의 적절한 위치에 삽입한다. 이를 위해 요소를 선택한 위치부터 왼쪽으로 이동하며, 선택한 요소보다 작은 요소를 찾을 때까지 계속해서 이동한다.
4. 삽입할 위치를 찾은 후 선택한 요소를 해당 위치에 삽입한다.
5. 정렬되지 않은 부분 배열의 다음 요소를 선택하고, 위의 단계를 반복한다.

  const arr = [8, 16, 88, 18, 343, 0, 100, 28, 90000, 0.5, 7, 13];
  function insertionSort(arr) {
    const n = arr.length;

    for (let i = 1; i < n; i++) {
      const current = arr[i];
      let j = i - 1;

      // 현재 요소보다 큰 요소를 만날 때까지 왼쪽으로 이동하며 삽입할 위치를 찾음
      while (j >= 0 && arr[j] > current) {
        arr[j + 1] = arr[j];
        j--;
      }

      // 삽입할 위치를 찾았으면 현재 요소를 삽입
      arr[j + 1] = current;
    }
  }

  // 예시 사용법
  console.log("정렬 전:", arr);
  insertionSort(arr);
  console.log("정렬 후:", arr);

 

3. Selection Sort(선택 정렬)

시간 복잡도를 항상 O(n^2)로 가지는 정렬 알고리즘이다. 간단하지만 비효율적인 알고리즘이다.

1. 배열의 첫 번째 요소를 선택합니다. 
2. 선택한 요소와 나머지 요소들을 하나씩 비교합니다. 
3. 가장 작은(또는 가장 큰) 요소를 찾아서 선택한 요소와 위치를 교환합니다. 
4. 다음 요소를 선택하고 위의 단계를 반복합니다. 즉, 두 번째, 세 번째 요소 등등을 차례로 선택하여 정렬합니다.

  const arr = [8, 16, 88, 18, 343, 0, 100, 28, 90000, 0.5, 7, 13];

  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]]; // ES6의 배열 분할 할당
      }
    }
  }

  // 예시 사용법
  console.log("정렬 전:", arr);
  selectionSort(arr);
  console.log("정렬 후:", arr);

 

4. Quick Sort

퀵소트는 분할 정복(Divide and Conquer) 방법을 기반으로, 매우 빠른 성능을 가지고 있는 정렬 알고리즘이다. 평균 시간 복잡도는 O(n log n)이다. 최악의 경우에는 O(n^2)이 나올 수 있다.

1. 배열에서 하나의 원소를 선택하여 이를 피벗(Pivot)으로 지정한다.
2. 피벗을 기준으로 배열을 분할한다. 피벗보다 작은 값은 피벗의 왼쪽에, 큰 값은 오른쪽에 위치시킨다. 이렇게 하면 피벗은 최종적으로 정렬된 위치에 오게 된다. 
3. 분할된 두 부분 배열에 대해 재귀적으로 위의 단계를 반복한다.
4. 재귀 호출을 통해 각 부분 배열을 정렬하여 마지막으로 전체 배열이 정렬된다.

  const arr = [8, 16, 88, 18, 343, 0, 100, 28, 90000, 0.5, 7, 13];
  function quickSort(arr) {
    if (arr.length <= 1) {
      return arr; // 기저 조건: 배열이 비어있거나 원소가 하나 이하일 경우 반환
    }

    const pivot = arr[0]; // 첫 번째 원소를 피벗으로 선택
    const left = [];
    const 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)]; // 왼쪽, 피벗, 오른쪽 배열을 재귀적으로 정렬하여 합침
  }

  // 예시 사용법
  console.log("정렬 전:", arr);
  const sortedArr = quickSort(arr);
  console.log("정렬 후:", sortedArr);