(알고리즘) 정렬- Bubble Sort, Selection Sort, Insertion Sort

정렬 알고리즘 중 가장 기본 적인 3가지를 정리해보겠습니다.

거품 정렬(Bubble Sort)

거품 정렬이란?

거품 정렬은 앞에서 부터 두 개의 아이템을 비교해 나가면서 둘 중 큰 값을 오른쪽 작은 값을 왼쪽으로 정렬하는 알고리즘 입니다.

구현(자바스크립트)

const bubbleSort = (arr) => {
  const length = arr.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
    // 왼쪽 아이템이 오른쪽 아이템 보다 크다면
      if (arr[j] > arr[j + 1]) {
        // 서로 교환
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
};

복잡도

• 시간복잡도: O(n^2)
  - 최선, 평균, 최악 모든경우가 다 O(n^2)의 복잡도를 가집니다.
• 공간복잡도: O(n)

장점

• 구현이 간단하고, 코드가 직관적입니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 입니다.

단점

• 어떤 상황에도 시간복잡도가 O(n^2)이라 굉장히 비효율 적입니다.
• 정렬 돼있지 않은 원소가 제자리를 찾아 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.

선택 정렬(Selection Sort)

선택 정렬은 먼저 배열의 첫 원소를 저장하고 나머지 원소들과 비교하여 해당 원소보다 작은값이 있으면 그값을 대신 저장해 가면서 가장 작은 값을 찾습니다. 이렇게 찾은 가장 작은 값을 배열의 시작점에 있는 값과 위치를 바꿔주고 다음 위치로 넘어가서 이 과정을 반복해 주는 알고리즘 입니다.
(다르게 표현하자면 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.)

구현(자바스크립트)

const selectionSort = (arr) => {
  const length = arr.length;
  for (let i = 0; i < length; i++) {
    let minIndex = i;
	// j가 i+1에서 시작하지 않으면 이미 정렬된 원소들까지 다시 과정에 포함시킵니다
    for (let j = i + 1; j < length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
};

복잡도

• 시간복잡도: O(n^2)
• 공간복잡도: O(n)

장점

• 단순한 알고리즘
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이라 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬

단점

• 비효율적
• 불안정 정렬(Unstable Sort) 입니다.

삽입 정렬(Insertion Sort)

실제 인간이 정렬하는 논리와 유사합니다.
두 번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교해가며, 타겟 원소의 값이 비교 원소값보다 크다면 비교 원소 뒤로 자리를 옮겨 주는 알고리즘 입니다.

구현(자바스크립트)

const insertionSort = (arr) => {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    // 시작점
    let current = arr[i];
    let j = i - 1;
    while (j > -1 && current < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
};

현재 원소(current)가 비교원소(arr[j])보다 작으면 비교원소를 하나씩 뒤로 밀어주고(arr[j+1]). 비교원소 보다 크거나 같으면 현재 원소를 비교원소 바로뒤로 옮겨준다(arr[j + 1] = current)

시간복잡도: O(n^2)

• 최선의 경우(모두 정렬이 되어있는 경우)는 O(n)이다.
  공간복잡도: O(n)

장점

• 단순한 알고리즘
• 대부분의 원소가 이미 정렬되있는 경우 효율적일 수 있습니다.
• 제자리 정렬
• 안정 정렬
• 같은 O(n^2)알고리즘 Selection Sort, Bubble Sort와 비교하여 상대적으로 빠릅니다.

단점

• 상대적으로 Selection Sort, Bubble Sort보다 빠를뿐 여전히 비효율적인 알고리즘 입니다.

참고- Tech Interview