가장 오래된 정렬 알고리즘의 하나로, 삽입정렬을 보완한 알고리즘

Goal

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

들어가기 전

셸 정렬(shell sort) 알고리즘의 개념 요약

셸 정렬(shell sort) 알고리즘의 구체적인 개념

셸 정렬(shell sort) 알고리즘의 예제

셸 정렬(shell sort) c언어 코드

# include <stdio.h>
# define MAX_SIZE 10

// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last까지
void inc_insertion_sort(int list[], int first, int last, int gap){
  int i, j, key;

  for(i=first+gap; i<=last; i=i+gap){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

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

    list[j+gap] = key;
  }
}

// 셸 정렬
void shell_sort(int list[], int n){
  int i, gap;

  for(gap=n/2; gap>0; gap=gap/2){
    if((gap%2) == 0)(
      gap++; // gap을 홀수로 만든다.
    )

    // 부분 리스트의 개수는 gap과 같다.
    for(i=0; i<gap; i++){
      // 부분 리스트에 대한 삽입 정렬 수행
      inc_insertion_sort(list, i, n-1, gap);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16};

  // 셸 정렬 수행
  shell_sort(list, n);

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

셸 정렬(shell sort) 알고리즘의 특징

셸 정렬(shell sort)의 시간복잡도

시간복잡도를 계산한다면

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

관련된 Post

References