데이터 구조 및 알고리즘-쉘 정렬

쉘 정렬은 매우 효율적인 정렬 알고리즘이며 삽입 정렬 알고리즘을 기반으로합니다. 이 알고리즘은 삽입 정렬의 경우처럼 작은 값이 맨 오른쪽에 있고 맨 왼쪽으로 이동해야하는 경우 큰 이동을 방지합니다.

이 알고리즘은 널리 퍼진 요소에 삽입 정렬을 사용하여 먼저 정렬 한 다음 덜 넓게 간격을 둔 요소를 정렬합니다. 이 간격은interval. 이 구간은 다음과 같은 Knuth의 공식을 기반으로 계산됩니다.

크 누스의 공식

h = h * 3 + 1
where −
   h is interval with initial value 1

이 알고리즘은 중간 크기의 데이터 세트에 대해 매우 효율적입니다.이 알고리즘의 평균 및 최악의 경우 복잡성은 가장 잘 알려진 갭 시퀀스에 따라 달라지며 여기서 n은 항목 수입니다. 그리고 최악의 공간 복잡도는 O (n)입니다.

쉘 정렬은 어떻게 작동합니까?

쉘 정렬이 어떻게 작동하는지 이해하기 위해 다음 예제를 고려해 보겠습니다. 이전 예제에서 사용한 것과 동일한 배열을 사용합니다. 예와 이해의 용이성을 위해 4의 간격을 사용합니다. 4 위치 간격에있는 모든 값의 가상 하위 목록을 만듭니다. 여기에서 이러한 값은 {35, 14}, {33, 19}, {42, 27} 및 {10, 44}입니다.

각 하위 목록의 값을 비교하고 필요한 경우 원래 배열에서 교체합니다. 이 단계가 끝나면 새 배열은 다음과 같아야합니다.

그런 다음 간격을 1로 설정하고이 간격은 두 개의 하위 목록 ({14, 27, 35, 42}, {19, 10, 33, 44})을 생성합니다.

필요한 경우 원래 배열에서 값을 비교하고 교체합니다. 이 단계 후에 배열은 다음과 같아야합니다.

마지막으로 값 1 간격을 사용하여 나머지 배열을 정렬합니다. 쉘 정렬은 삽입 정렬을 사용하여 배열을 정렬합니다.

다음은 단계별 묘사입니다.

나머지 어레이를 정렬하는 데 4 개의 스왑 만 필요하다는 것을 알 수 있습니다.

연산

다음은 쉘 정렬 알고리즘입니다.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

의사 코드

다음은 쉘 정렬을위한 의사 코드입니다.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

C 프로그래밍 언어의 쉘 정렬 구현에 대해 알아 보려면 여기 를 클릭하십시오 .