Shell 정렬

1. Shell 정렬 알고리즘
2. Shell 정렬 예
3. Shell 정렬 알고리즘 구현
4. Shell 정렬 알고리즘 복잡성

Shell 정렬은 매우 효율적인 비교 기반 정렬 알고리즘입니다. 버블 정렬 알고리즘의 일반화 또는 최적화 된 삽입 정렬 알고리즘으로 간주됩니다. 삽입 정렬 알고리즘에서 요소를 한 위치 앞으로 이동합니다. 그러나 Shell 정렬의 경우 요소 h위치를 앞으로 이동합니다. 매우 먼 요소를 정렬하는 것으로 시작하여 전체 배열을 정렬하는 순서에 따라 간격을 점차적으로 줄입니다. 사용되는 일부 시퀀스는 다음과 같습니다.

Shell 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 셸의 원래 시퀀스를 사용하여 배열을 정렬합니다.

Shell 정렬 예

배열이(9, 8, 3, 7, 5, 6, 4, 1)이라고 가정합니다. Shell 정렬 알고리즘을 사용하여 정렬하고 쉘의 원래 시퀀스를 사용하여 간격 간격을 줄입니다.

• 첫 번째 반복

n/2 = 4, 간격4에있는 요소가 비교되고 교체됩니다.

A[0]>A[4]→ 교체 됨,(5,8,3,7,9,6,4,1).

A[1]>A[5]→ 교체 됨,(5,6,3,7,9,8,4,1).

A[2]<A[6]

A[3]>A[7]→ 교체 됨,(5,6,3,1,9,8,4,7).

배열은(5,6,3,1,9,8,4,7)이됩니다.

• 두 번째 반복

n/4 = 2,2 간격에있는 요소가 비교되고 교체됩니다.

A[0]>A[2]→ 교체 됨,(3,6,5,1,9,8,4,7).

A[1]>A[3]→ 교체 됨,(3,1,5,6,9,8,4,7).

A[0]<A[2]<A[4]

A[1]<A[3]<A[5]

A[2]>A[4]및A[4]>A[6]→ 교체 됨,(3,1,4,6,5,8,9,7).

A[1]<A[3]<A[5]그러나A[5]>A[7]→ 교체 됨,(3,1,4,6,5,7 , 9,8).

배열은(3,1,4,6,5,7,9,8)이됩니다.

• 세 번째 반복

n/8 = 1,1 간격에있는 요소가 비교되고 교체됩니다.

A[0]> A[1]→ 교체 됨,(1,3,4,6,5,7,9,8).

A[0] .. A[2]→ 정렬 됨

A[0] .. A[3]→ 정렬 됨

A[0] .. A[3]→ 정렬되었지만 A[3]> A[4] → 교체 됨,(1,3,4,5,6,7,9,8).

A[0] .. A[5]→ 정렬 됨

A[0] .. A[6]→ 정렬 됨

A[0] .. A[6]→ 정렬되었지만 A[6]> A[7] → 교체 됨,(1, 3, 4, 5, 6, 7, 8, 9).

Shell 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Shell 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

복잡성은 정렬을 위해 선택한 순서에 따라 다릅니다. 시간 복잡도는 [Big Theta] : O(nlog(n)²)의 순서입니다.

• 최악의 경우

Shell 정렬의 최악의 경우 시간 복잡도는 항상 O(n²)보다 작습니다. 더 정확하게 Poonen의 정리에 따르면 Θ(nlogn)²/(log log n)²) 또는 Θ(nlog n)²/log log n) 또는 Θ(n(log n)²) 또는 그 사이에 있습니다. 최악의 경우 시간 복잡도는 [Big O] : O(n²)보다 작습니다.

• 베스트 케이스

최상의 경우는 배열이 이미 정렬되어 있고 각 간격에 필요한 비교가 배열의 크기와 같을 때 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(nlogn)입니다.

공간 복잡성

Shell 정렬 알고리즘의 공간 복잡성은 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(n)입니다.