이번 포스팅에서는 쉘 정렬 알고리즘에 대해 알아보겠습니다. 쉘 정렬은 삽입 정렬의 일반화로, 여러 위치의 간격으로 분리된 요소를 비교하여 삽입 정렬의 단점을 극복합니다.
삽입 정렬의 확장 버전인 정렬 알고리즘입니다. 쉘 정렬은 삽입 정렬의 평균 시간 복잡성을 개선했습니다. 삽입 정렬과 유사하게 비교 기반 및 내부 정렬 알고리즘입니다. 쉘 정렬은 중간 크기의 데이터 세트에 효율적입니다.
삽입 정렬에서는 요소를 한 번에 한 위치씩 앞으로 이동할 수 있습니다. 요소를 멀리 있는 위치로 이동하려면 많은 이동이 필요하며 알고리즘의 실행 시간이 늘어납니다. 그러나 쉘 정렬은 삽입 정렬의 이러한 단점을 극복합니다. 멀리 있는 요소의 이동 및 교환도 가능합니다.
이 알고리즘은 먼저 서로 멀리 떨어져 있는 요소를 정렬한 다음 그 사이의 간격을 줄입니다. 이 간격을 다음과 같이 부릅니다. 간격. 이 간격은 다음을 사용하여 계산할 수 있습니다. 크누스의 아래 주어진 공식 -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
이제 쉘 정렬 알고리즘을 살펴보겠습니다.
연산
쉘 정렬을 수행하는 간단한 단계는 다음과 같습니다.
ShellSort(a, n) // 'a' is the given array, 'n' is the size of array for (interval = n/2; interval > 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>
Shell 정렬 알고리즘의 작동
이제 쉘 정렬 알고리즘의 작동을 살펴보겠습니다.
쉘 정렬 알고리즘의 작동을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 예제를 통해 쉘 정렬을 이해하는 것이 더 쉬울 것입니다.
배열의 요소는 다음과 같습니다.
우리는 쉘 정렬의 원래 시퀀스, 즉 N/2, N/4,...,1을 간격으로 사용합니다.
첫 번째 루프에서 n은 8(배열 크기)과 같으므로 요소는 4(n/2 = 4) 간격으로 배치됩니다. 요소는 순서가 맞지 않으면 비교되고 교체됩니다.
여기 첫 번째 루프에서 0에 있는 요소는일위치는 4의 요소와 비교됩니다.일위치. 0인 경우일요소가 더 크면 4에 있는 요소로 교체됩니다.일위치. 그렇지 않으면 동일하게 유지됩니다. 이 프로세스는 나머지 요소에 대해 계속됩니다.
4 간격에서 하위 목록은 {33, 12}, {31, 17}, {40, 25}, {8, 42}입니다.
이제 모든 하위 목록의 값을 비교해야 합니다. 비교한 후 필요한 경우 원래 배열에서 교체해야 합니다. 비교하고 교체한 후 업데이트된 배열은 다음과 같습니다.
두 번째 루프에서는 요소가 2(n/4 = 2) 간격으로 놓여 있습니다. 여기서 n = 8입니다.
이제 우리는 2 배열의 나머지 부분을 정렬합니다. 간격이 2이면 두 개의 하위 목록({12, 25, 33, 40} 및 {17, 8, 31, 42})이 생성됩니다.
이제 다시 모든 하위 목록의 값을 비교해야 합니다. 비교한 후 필요한 경우 원래 배열에서 교체해야 합니다. 비교하고 교체한 후 업데이트된 배열은 다음과 같습니다.
arp 명령
세 번째 루프에서는 요소가 1(n/8 = 1) 간격으로 놓여 있으며 여기서 n = 8입니다. 마지막으로 값 1의 간격을 사용하여 나머지 배열 요소를 정렬합니다. 이 단계에서 쉘 정렬은 삽입 정렬을 사용하여 배열 요소를 정렬합니다.
이제 배열이 오름차순으로 정렬되었습니다.
쉘 정렬 복잡성
이제 쉘 정렬의 시간 복잡도를 최상의 경우, 평균적인 경우, 최악의 경우로 살펴보겠습니다. 또한 Shell 정렬의 공간 복잡도도 살펴보겠습니다.
1. 시간 복잡도
| 사례 | 시간 복잡도 |
|---|---|
| 최선의 경우 | O(n*logn) |
| 평균 사례 | O(n*log(n)2) |
| 최악의 경우 | 에2) |
2. 공간 복잡성
| 공간 복잡도 | 오(1) |
| 안정적인 | 아니요 |
- 쉘 정렬의 공간 복잡도는 O(1)입니다.
쉘 정렬 구현
이제 다양한 프로그래밍 언어로 작성된 Shell sort 프로그램을 살펴보겠습니다.
프로그램: C 언어로 쉘 정렬을 구현하는 프로그램을 작성하세요.
#include /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 42 i++) printf('%d ', a[i]); } int main() { a[]="{" 33, 31, 40, 8, 12, 17, 25, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); shell(a, printf('
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-7.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C++.</p> <pre> #include using namespace std; /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 41 i++) cout< <a[i]<<' '; } int main() { a[]="{" 32, 30, 39, 7, 11, 16, 24, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); shell(a, cout<<'
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-8.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C#.</p> <pre> using System; class ShellSort { /* function to implement shellSort */ static void shell(int[] a, int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int[] a, int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 40 i++) console.write(a[i] + ' '); } static void main() { int[] a="{" 31, 29, 38, 6, 10, 15, 23, }; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); shell(a, console.write('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-9.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in Java.</p> <pre> class ShellSort { /* function to implement shellSort */ static void shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval > 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 39 i++) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{" 30, 28, 37, 5, 9, 14, 22, }; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); shell(a, system.out.print('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-10.webp" alt="Shell Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>