Shell sort (쉘 정렬)

쉘 정렬

    - 삽입 정렬의 문제점

        * 삽입할 위치가 현재 삽입할 요소와 멀리 떨어져 있다면, 많은 요소들을 옮겨야 함

 

    - 삽입 정렬의 문제점을 보완하는 정렬

    - 쉘 정렬은 특정 간격(k)에 있는 요소들을 부분 배열으로 하고 삽입 정렬을 진행하여 정렬

 

    - 쉘 정렬의 원리

        * 배열의 요소들이 정렬되어 있으면 삽입 정렬의 시간복잡도 O(N)

        * 배열의 요소들을 어느 정도 정렬 시켜 놓으면 삽입 정렬은 빠름

        * 어느 정도 정렬 시키기 위해서 배열을 간격 별로 모아서 부분 배열을 만들어 정렬

 

 

 

동작

    - 초기 간격(k)를 구함 : 정렬할 배열의 길이 / 2

    - 간격(k) 만큼 떨어진 요소들을 부분 집합으로 하고 삽입 정렬

    - 위 과정으로 한 번의 정렬이 끝나면, k = k / 2 하여 위 과정 반복

    - 간격(k)의 크기가 1이 될 때까지 반복

 

    - 예시

        * 1번 : 간격(k=4)로 부분 배열을 만들고, 부분 배열 내에서 삽입 정렬 진행

 

        * 2번 : 간격(k=2)로 부분 배열을 만들고, 부분 배열 내에서 삽입 정렬 진행

 

        * 3번 : k=1일 때, 전체가 부분 배열이 되어, 마치 삽입 정렬을 하는 것과 같음

 

구현

// 시작 인덱스부터 gap 간격에 있는 요소들로 부분 배열을 만들어 삽입 정렬  
int gap_insertion_sort(int list[], int first, int last, int gap){
    
  int i, j, value;
 
  // 삽입 정렬은 두 번째 인뎃스부터 진행하므로
  // 시작 인뎃스는 first + gap  
  for (i = first + gap; i <= last; i += gap)
  {
    // 삽입할 요소 선택  
    value = list[i];
 
    // 삽입할 value 이전에 있는 요소들과 비교 
    // 요소들은 간격 단위로 위치하므로 j -= gap으로 이동 
    // 이동 인덱스 j는 시작 위치 first와 같거나 커야 하고
    // 비교되는 list[j]의 값은 삽입할 value보다 커야 한다. 
    for (j = i - gap; j >= first && list[j] > value; j -= gap)
    {
      // 비교되는 list[j]가 삽입할 value보다 크다면 뒤로 옮긴다.
      // 옮길 때는 gap 간격으로 옮긴다. 
      list[j + gap] = list[j];
    }
    
    // 멈춘 곳에 삽입할 value를 삽입한다. 
    list[j + gap] = value;
  }
  
}
 
// 쉘 정렬
int shell_sort(int list[], int n){
    
  int gap, i;
 
  // 초기 gap은 배열 크기의 1/2
  // 이후 gap을 1/2 해준다. 
  for (gap = n/2; gap > 0; gap /= 2){
 
    // 배열의 i번째부터 gap 간격에 있는
    // 요소들을 찾아서 삽입 정렬 
    for (i = 0; i < gap; i++)
      gap_insertion_sort(list, i, n - 1, gap);
  }
  
}

 

특징

    - 간격(k)에 의해 만들어진 비연속적은 부분 배열에서 삽입 정렬이 일어나기 때문에 요소들은 더 큰 거리를 이동한다. 더 큰 거리를 이동했다는 의미는 선택된 요소가 최종 위치에 더 가깝게 배치된다는 뜻이다. 따라서 연산량이 줄어 더 빠르다.

 

    - 간격(k)를 결정하는 방법은 여러 가지 이다. 일반적으로 간격을 반으로 나누거나, 반으로 나누어서 + 1 하여 홀수로 만든다. 

 

    - 삽입 정렬은 정렬된 배열에서 빠르게 정렬하는 특징이 있다. 쉘 정렬에서는 부분 배열을 만들기 때문에 큰 배열보다 정렬할 요소가 적어서 덜 복잡하다고 할 수 있다. 덜 복잡한 부분 배열을 삽입 정렬로 처리하면서 전체 배열을 정렬로 만든다. 따라서 삽입 정렬보다 더 빠르다.

 

 

 

참고

    - 블로그 1

    - 블로그 2

    - 블로그 3

    - 위키피디아