☀️ 알고리즘:: 정렬 알고리즘_ 선택 정렬과 삽입 정렬

April·2021년 10월 25일
0
post-thumbnail

🚀 What I Will Learn

  • 선택 정렬 의 원리를 이해한다
  • 삽입 정렬 의 원리를 이해한다

컴퓨터 과학과 수학에서 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.



정렬 알고리즘

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²)인 가장 간단한 형태의 정렬 알고리즘이다
profile
🚀 내가 보려고 쓰는 기술블로그

0개의 댓글