손안의 카드를 정렬하는 방법과 유사한 알고리즘

Goal

  • 삽입 정렬(insertion sort) 알고리즘을 이해한다.
  • 삽입 정렬(insertion sort) 알고리즘을 c언어로 구현한다.
  • 삽입 정렬(insertion sort) 알고리즘의 특징
  • 삽입 정렬(insertion sort) 알고리즘의 시간복잡도를 이해한다.

들어가기 전

삽입 정렬(insertion sort) 알고리즘 개념 요약

삽입 정렬(insertion sort) 알고리즘의 구체적인 개념

삽입 정렬(insertion sort) 알고리즘의 예제

삽입 정렬(insertion sort) c언어 코드

# include <stdio.h>
# define MAX_SIZE 5

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {8, 5, 6, 2, 4};

  // 삽입 정렬 수행
  insertion_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

삽입 정렬(insertion sort) 알고리즘의 특징

삽입 정렬(insertion sort)의 시간복잡도

시간복잡도를 계산한다면

정렬 알고리즘 시간복잡도 비교

관련된 Post

References