[2주차 TIL] KnockOn Bootcamp 정렬 알고리즘

• 버블 정렬
• 선택 정렬
• 삽입 정렬

정렬 알고리즘

정렬(sorting)이란 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 것이다. 정렬에도 여러 가지 방법들이 있는데 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있다.

---

버블 정렬(Bubble sort)

버블 정렬은 가장 간단한 정령 알고리즘 중 하나이다.
간단하게, 옆에 위치한 두 개끼리 비교하여 정렬하는 것을 반복하는 것이다.

예시를 들어

arr[] = {6,0, 3, 5}
이면

• 1. 가장 큰 element가 끝으로 위치하게 된다.

• 2. 두 번째 큰 element도 제 위치를 찾아가게 된다.

• 3. 세 번째 큰 element도 제 자리를 찾아가므로, element개수가 총 4개인 이 배열은 정렬이 완료되었다.

버블 정렬의 구현

#include <stdbool.h>
#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

// 버블 정렬
void bubbleSort(int arr[], int n) {
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        swapped = true;
      }
    }
    // 이 경우 처음부터 정렬되어있었음
    if (swapped == false)
      break;
  }
}

// 배열 출력
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

int main(void) {
  int arr[] = {64, 34, 25, 12, 22, 11, 99};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printArray(arr, n);
  return 0;
}

위와 같이 구현할 수 있다.
실행 시 작은 값부터 출력된다.

버블 정렬 분석

이중반복문을 돌기 때문에 시간복잡도는 $$ O(N^2) $$

장점

• 가장 간단한 정렬 알고리즘 중 하나이다.
• 추가적인 메모리 공간이 필요없다.
• stable하다.

단점

• $O(N^2)$의 시간복잡도
• comparison operator가 요구됨.

stable

크기가 같은 값이 있을 때, 예를 들어 12가 두 개면 하나를 a1, 남은 하나를 a2라 하자.
정렬은 크기를 기준으로 하기 때문에 값이 같은 a1과 a2는 경우에 따라 서로 위치가 a2, a1처럼 바뀔 수도 있는데, 바뀌지 않는 경우를 stable하다고 한다.

---

선택 정렬(Selection Sort)

선택 정렬도 마찬가지로 간단하고 효과적인 정렬 알고리즘 중 하나이다. 선택 정렬은 계속해서 가장 작은 값 또는 가장 큰 값을 뽑아내서 끝의 위치로 옮겨준다.

마찬가지로 예시를 보면
arr = {64, 25, 12, 22, 11}

• 1. 최솟값을 탐색한다. 가장 작은 값은 11이다.

• 2. 11을 64의 자리로 옮긴다. 11은 정렬되었으니 건드리지 말고 다음 작은 값을 찾는데 이건 12이다.

• 3. 과정은 계속 같다...이번에는 22가 가장 작다. 22를 25와 교환해준다.

• 4. 25가 최솟값이고, 이미 4번째 자리에 있어서 교환해줄 필요는 없다.

• 5. 이미 위에서 3번 시점에서 이 배열은 정렬된 상태이지만, 이러한 과정을 통해 최종적으로 가장 큰 값이 자동적으로 맨 뒤에 오게되면서 정렬이 완료된다.

선택 정렬의 구현

#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void selectionSort(int arr[], int n) {
  int min_idx;
  for (int i = 0; i < n - 1; i++) {
    min_idx = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;
    if (min_idx != i)
      swap(&arr[min_idx], &arr[i]);
  }
}

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {190, 90, 120, 1, 3, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  selectionSort(arr, n);
  printArray(arr, n);
  return 0;
}

선택 정렬 분석

시간복잡도는 이중반복문을 돌게 되므로
$$O(N^2)$$

장점

• 간단하다. 버블정렬과 마찬가지로..
• 작은 데이터셋에서 잘 작동한다.

단점

• 시간복잡도.
• 큰 데이터셋에서는 좋지 못하다.
• stable하지 않다.

---

삽입 정렬(Insertion Sort)

삽입 정령은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 element를 찾고, 그 element를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘이다.

1. 첫 번째 요소가 정렬이 되어있다고 가정하고 두 번째 요소부터 살펴본다.
2. 첫 번째 요소와 두 번째 요소를 비교한다. 비교 후 swap으로 정렬
3. 세 번째 요소와 두 번째 요소를 비교하고, 다음으로 첫 번째 요소와 비교한다. 그리고 세 번째 요소를 맞는 위치에 끼워넣는다.
4. 이런 식으로 완전히 정렬되기 전까지 반복한다.

사진의 예시를 살펴보고 위 절차대로 수행해보자.

23이 정렬되어있다고 가정하고 1과 23을 비교
-> 1을 23 앞에 끼워넣기
-> 10과 23 비교, 10과 1 비교. 1과 23 사이에 끼워넣음
-> 5도 마찬가지로 비교해서 끼워넣음.
-> 2도 순차적으로 비교해서 맞는 위치에 끼워넣음.
-> 정렬 완료

삽입 정렬의 구현

#include <stdio.h>

void insertionSort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

void printArray(int arr[], int n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);
  insertionSort(arr, n);
  printArray(arr, n);
  return 0;
}

삽입 정렬 분석

• Best Case: $O(N)$
• Average Case: $O(N^2)$
• Worst Case: $O(N^2)$

이미 전부 정렬되어 있는 경우 O(N)이지만 랜덤하게 되어있거나, 역순으로 되어있는 최악의 경우일 때는 $O(N^2)$

장점

• 간단하다.
• stable
• 작은 크기의 리스트에 적합하다.

단점

• 큰 크기에서는 적합하지 않음
• 위 두 알고리즘에 비교한 단점은 아니나 일반적으로 머지 소트나 퀵 소트가 더 효율적이다.