[study] 정렬 - 선택정렬, 삽입정렬, 버블정렬

먼저 알고 가야 할 개념!

✅️ Stable 정렬 ❓️

정렬을 했을 때 중복된 값들의 순서가 변하지 않는 것을 말한다.

만약, arr = [1, 7(1), 3, 5, 4, 7(2), 9] 을 정렬한 결과가

arr = [1, 3, 4, 5, 7(1), 7(2), 9] 이면 Stable(안정)
arr = [1, 3, 4, 5, 7(2), 7(1), 9] 이면 Unstable(불안정)

이라 할 수 있다.

✅️ In-place 정렬 ❓️

정렬하는데 추가적인 메모리 공간이 거의 들지 않는 것을 말한다.
제자리 정렬이라고도 한다.

---

1️⃣️ 선택 정렬(Selection Sort)

선택 정렬은 배열의 최솟값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌다.
선택 정렬은 in-place 알고리즘이다.
때문에 다른 추가적인 메모리를 요구하지 않는다.
매 회전의 초기마다 idx 를 통해 현재 인덱스를 저장하고,
이후에 자기보다 뒤에 있는 인덱스를 순회하면서 최소값을 가지는 인덱스를 찾는 방식으로 진행된다.

예시코드

function selectionSort(arr) {
  let indexMin;
  for (let x = 0; x < arr.length - 1; x++) {
    indexMin = x;
    for (let y = x + 1; y < arr.length; y++) {
      if (arr[y] < arr[indexMin]) {
        indexMin = y;
      }
    }
    [arr[x], arr[indexMin]] = [arr[indexMin], arr[x]];
  }
  return arr;
}

선택 정렬은 앞쪽부터 정렬하는 방식으로,

• 주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다.
• 맨 앞의 값을 제외한 배열로 다시 반복한다.

👍 장점

• 구현이 간단하다.
• 비교하는 횟수에 비해 교환하는 횟수가 적기 때문에, 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬.

👎 단점

• 데이터를 하나씩 비교하기 때문에 시간복잡도가 O(n^2)으로, 비효율적이다.
• Unstable 정렬이다. (구현하는 방식에 따라 달라질 수 있음)
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.

---

2️⃣️ 버블 정렬

버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식.

i번째 원소와 i+1번째 원소의 값을 비교하고 만약 i번째의 값이 i+1번째의 값보다 크다면 둘의 자리를 바꾸어 값이 큰 원소가 뒤에 위치하게 됨!
이를 반복해서 수행하면 가장 큰 값부터 뒤쪽에 쌓인다.
즉 가장 큰값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬하는 것.

정렬 방식이 마치 물속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다고 한다.

예시코드

function bubbleSort(arr) {
  for (let x = 0; x < arr.length; x++) {
    for (let y = 1; y < arr.length - x; y++) {
      if (arr[y - 1] > arr[y]) {
        [arr[y - 1], arr[y]] = [arr[y], arr[y - 1]];
      }
    }
  }

  return arr;
}

👍 장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬
• Stable 정렬

👎 단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적.
• 데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸리기 때문.
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.

개선된 버블 정렬

칵테일 셰이커(Cocktail Shaker) 정렬 (= 양방향 버블 정렬)

버블 정렬과는 달리 매 반복마다 배열의 순서를 바꾸어 정렬함.
홀수 번째 반복은 가장 작은 요소를 맨 앞으로, 짝수 번째 반복은 가장 큰 요소를 맨 뒤로 정렬한다.(또는 반대)
시간복잡도는 최선의 경우 O(n)을 만족함.
평균과 최악의 경우 여전히 O(n^2).

---

3️⃣️ 삽입 정렬(Insertion Sort)

삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법이다.

버블 정렬은 i번째와 i+1번째를 비교하며 위치를 바꾸었다면, 삽입 정렬은 i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입하는 방식이다.

i-1번째 원소까지는 모두 정렬된 상태여야 하며 i-1번째부터 0번째까지의 원소와 i번째 원소를 각각 비교한다.
이때 i번째 원소보다 작은 값이 발견되면 그 위치에 i번째 원소를 삽입한다.

삽입 정렬은 버블 정렬의 비교 및 교환 횟수를 줄임으로써 높은 효율을 보여준다.

예시코드

function insertionSort(arr) {
  for (let x = 1; x < arr.length; x++) {
    let value = arr[x];
    let prev = x - 1;
    while (prev >= 0 && arr[prev] > value) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = value;
  }

  return arr;
}

👍 장점

• 입력으로 들어오는 배열의 원소가 정렬되어있을수록 속도가 빠르다.
• 정렬된 값은 교환이 일어나지 않는다.
• 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘!
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로 In-place 정렬.
• Stable 정렬입니다.
• 선택 정렬, 버블 정렬과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

👎 단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• 선택 정렬, 버블 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다.