정렬 알고리즘

1️⃣ 선택 정렬이란?

1) 가장 기본적인 정렬 알고리즘 2) 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법 3) 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 O(n²)의 시간복잡도를 가진다

정렬 전

정렬 후

2️⃣ 선택 정렬의 구현

1) 배열 선언

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#define SIZE 1000

int a[SIZE];
int swap(int *a, int *b) { 
  int temp = *a;
  *a = *b;
  *b = temp;
}

2) 선택정렬수행

int main(void) {
  int n, min, index;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]); 
  for (int i = 0; i < n; i++) {
    min = INT_MAX;
    for (int j = i; j < n; j++) {
      if (min > a[j]) {
        min = a[j];
        index = j;
      } 
    }
    swap(&a[i], &a[index]); 
  }
  system("pause");
  return 0; 
}

3️⃣ 삽입 정렬이란?

1) 각 숫자를 적절한 위치에 삽입하는 정렬 기법 2) 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번이므로 O(n²)의 시간복잡도를 가진다 3) 일반적으로 선택 정렬보다 빠르게 동작한다

정렬 전

정렬 중
- 두 번째 원소인 4부터 출발해서 4가 들어갈 공간을 확인한다
- 그 다음인 3은 2와 4의 위치를 확인했을 때에 2와 4의 사이에 들어간다

정렬 후

4️⃣ 삽입 정렬의 구현

1) 배열 선언

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a[SIZE];
int swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

2) 삽입정렬수행

int main(void) {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]); 
  for (int i = 0; i < n - 1; i++) {
      int j = i;
      while (j >= 0 && a[j] > a[j + 1]) {
        swap(&a[j], &a[j + 1]);
  	j--; 
      }
  } 
  system("pause"); 
  return 0;
}

✨ tl;dr

선택 정렬과 삽입 정렬은 시간복잡도가 O(n²)인 가장 간단한 형태의 정렬 알고리즘이다