[ Algorithm ] 정렬 알고리즘

1. 선택정렬(Selection Sort)

단계별로 정렬을 수행할때 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법이다.

앞으로 보내진 원소는 위치가 변경되지 않고 시간복잡도 O(N²)으로 비효율적인 알고리즘에 속한다.

 

동작방식

1. 단계별로 수행하면서 가장 작은 원소를 선택한다.

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;
  }
}

 

 

2. 버블정렬(Bubble Sort)

인접한 두 원소를 체크하여 정렬이 안되어 있다면 위치를 서로 변경하는 정렬방식이다.

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

시간복잡도 O(N²)으로 비효율적인 정렬 알고리즘에 속한다.

 

동작방식

1. 단계별로 수행하면서 가장 큰 원소가 맨 뒤로 이동한다.

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;
      }
    }
  }
}

 

 

3. 삽입정렬(Insertion Sort)

각 원소를 적절한 위치에 삽입하는 정렬이다.

 

동작방식

1. 단계별로 수행하면서 현재 원소가 삽입될 위치를 탐색한다.

2. 지정 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.

 

• 삽입정렬 함수 예시

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      // 시작인덱스부터 1까지 1씩 감소하며 반복
      if (arr[j] < arr[j - 1]) {
        let temp = arr[j];
        arr[j] = arr[j - 1]; // 한 칸씩 왼쪽으로 이동
        arr[j - 1] = temp; // 스왑(swap)
      } else {
        break; // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      }
    }
  }
}

 

 

4. 병합정렬(Merge Sort)

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

 

분할정복이란?

• 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할한다.
• 정복(conquer): 작은 부분 문제를 각각해결하도록 한다.
• 조합(combine): 해결한 작은 부분의 답을 이용하여 큰 문제를 해결해나간다.

일반적으로 재귀함수를 사용하여 구현한다.

큰 문제를 작은 문제로 분할하는 방식이 같은 경우가 많기 때문이다.

그렇기 때문에 쪼개질 수 없는 크기가 될 때까지 계속해서 분할한다.

 

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

단점: 전반적으로 정복과정에서 임시배열이 필요한 경우가 지배적이다.

 

동작방식

1. 단계별로 수행하면서 현재 원소가 삽입될 위치를 탐색한다.

2. 지정 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.

 

• 병합정렬 함수 예시

function merge(left, right) {
  let sorted = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) sorted.push(left.shift());
    else sorted.push(right.shift());
  }
  return [...sorted, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  let half = Math.ceil(arr.length / 2);
  let left = arr.slice(0, half);
  let right = arr.slice(half);
  return merge(mergeSort(left), mergeSort(right));
}

let arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);

console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4, 5, 6, 7]

function merge: 이미정렬된 배열 left와 right를 하나의 함수로 합쳐주는 순수 함수

function mergeSort: 배열을 반으로 나누어 merge함수에게 left와 right로 전달한다.

 

 

마치며...

오늘 포스팅한 정렬알고리즘은 사실, 알고리즘을 따로 공부를하기전까진 단순하게 정렬하는거지! 라고 생각했지만 정말 다양하고 어떤방식으로 정렬을 하느냐에 따라 시간복잡도가 제곱이상의 차이가 나기도 한다는 것이 새롭게 다가왔던 것 같다. 앞으로도 코드의 퀄리티를 위해서 프로젝트에서 정렬할때 잘 생각해보고 적용시켜야겠다.