[Algorithm] 정렬 알고리즘-1(selection, Bubble, Insertion)

Dongjun Ahn·2023년 9월 26일

정렬알고리즘은 컴퓨터 공학에서 중요시되는 문제 중 하나로, 어떤 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 문제이다.

실제 개발을 하다보면 불규칙한 데이터들을 정렬 후 탐색해야하는 경우가 꽤나 많이 발생하게 되는데 이때 상황에 맞는 알고리즘을 사용하여 효과적으로 문제를 해결할 수 있느냐가 핵심이라고 볼 수 있다.

시간복잡도가 O(2ⁿ)인 정렬 알고리즘은 크게 3가지가 있다
1. 선택 정렬(Selection sort)
2. 버블 정렬(Bubble sort)
3. 삽입 정렬(Insertion sort)

선택 정렬(Selection Sort)

가장 작은것을 선택해서 제일 앞으로 이동시키는 알고리즘

선택정렬은 주어진 자료들 중에 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 정렬 알고리즘이다. 한번 순회를 돌게되면 알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로 그 다음 순회부터는 1번 인덱스부터 순회를 돌며 반복하면 된다.

순서

0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 swap한다
1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 swap한다
…
n-1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 swap한다

예제

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

버블 정렬(Bubble sort)

다음 값과 비교하여 작은것을 앞으로 큰것을 뒤로 이동시키는 알고리즘

버블정렬은 거의 모든 상황에서 최악의 성능을 보여주지만, 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다. 이미 정렬되어 있는 데이터를 왜 정렬하냐는 의문이 들 수 있지만, 정렬알고리즘 자체는 데이터가 정렬되어 있는지 아닌지 모르고 작동하는 것이기 때문에 의미는 있다.

순서

0번째 원소와 1번째 원소를 비교 후 정렬
1번째 원소와 2번째 원소를 비교 후 정렬
…
n-1번째 원소와 n번째 원소를 비교 후 정렬

예제

function bubbleSort (input) {
  const len = input.length;
  let tmp = null;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (input[j] > input[j + 1]) {
        // Swap
        tmp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = tmp;
        tmp = null;
      }
    }
	if (!tmp) {
      break;
    }
  }
  return input;
}

삽입정렬(Insertion sort)

왼쪽에서 오른쪽으로 가면서 각 요소를 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 알고리즘

삽입정렬은 주어진 자료의 모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.

삽입정렬은 최선의 경우 전체 자료를 한번만 순회하면 되기때문에 O(n)의 시간복잡도를 가지지만 최악의 경우 O(2ⁿ)의 시간복잡도를 가진다.

순서

2번째 인덱스부터 시작하여 그앞의 원소와 비교하여 정렬.
3번째 인덱스와 그앞의 원소들과 비교하여 정렬.
...
n번째 인덱스와 그앞의 원소들을 비교하여 정렬.

예제

function insertionSort (input) {
  const len = input.length;
  for (let i = 1; i < len; i++) { 
    const value = input[i]; 
    let j = i-1;
    for (;j > -1 && input[j] > value; j--) {
      input[j+1] = input[j];
    }
    input[j+1] = value;
  }
  return input;
}