في هذه المقالة، سنناقش خوارزمية فرز الصدفة. فرز الصدفة هو تعميم لفرز الإدراج، والذي يتغلب على عيوب فرز الإدراج من خلال مقارنة العناصر المفصولة بفجوة في عدة مواضع.
إنها خوارزمية فرز وهي نسخة موسعة من فرز الإدراج. أدى فرز Shell إلى تحسين متوسط التعقيد الزمني لفرز الإدراج. على غرار فرز الإدراج، فهي خوارزمية فرز قائمة على المقارنة وفي المكان. يعد فرز Shell فعالاً لمجموعات البيانات متوسطة الحجم.
في فرز الإدراج، في المرة الواحدة، يمكن نقل العناصر للأمام بمقدار موضع واحد فقط. لنقل عنصر إلى موضع بعيد، يلزم إجراء العديد من الحركات التي تزيد من وقت تنفيذ الخوارزمية. لكن فرز الصدفة يتغلب على هذا العيب المتمثل في فرز الإدراج. فهو يسمح بحركة وتبديل العناصر البعيدة أيضًا.
ترينج إلى كثافة العمليات
تقوم هذه الخوارزمية أولاً بفرز العناصر البعيدة عن بعضها البعض، ثم تقوم بعد ذلك بتقليص الفجوة بينها. وتسمى هذه الفجوة باسم فاصلة. ويمكن حساب هذه الفترة باستخدام نوث الصيغة الواردة أدناه -
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;>
عمل خوارزمية فرز شل
الآن دعونا نرى كيفية عمل خوارزمية فرز الصدفة.
لفهم عمل خوارزمية فرز الصدفة، لنأخذ مصفوفة غير مصنفة. سيكون من الأسهل فهم نوع الصدفة من خلال مثال.
دع عناصر المصفوفة هي -
سوف نستخدم التسلسل الأصلي لفرز الصدفة، أي N/2، N/4،....،1 كفواصل زمنية.
في الحلقة الأولى، n يساوي 8 (حجم المصفوفة)، وبالتالي فإن العناصر تقع عند الفاصل الزمني 4 (n/2 = 4). ستتم مقارنة العناصر وتبديلها إذا لم تكن بالترتيب.
هنا، في الحلقة الأولى، العنصر عند 0ذسيتم مقارنة الموضع بالعنصر عند 4ذموضع. إذا كان 0ذالعنصر أكبر، سيتم تبديله بالعنصر عند 4ذموضع. وبخلاف ذلك، يبقى الأمر على حاله. ستستمر هذه العملية بالنسبة للعناصر المتبقية.
عند الفاصل الزمني 4، تكون القوائم الفرعية هي {33، 12}، {31، 17}، {40، 25}، {8، 42}.
كيفية حذف العمود في postgresql
الآن، علينا مقارنة القيم في كل قائمة فرعية. بعد المقارنة، يتعين علينا تبديلها إذا لزم الأمر في المصفوفة الأصلية. بعد المقارنة والتبديل، سوف تبدو المصفوفة المحدثة كما يلي -
في الحلقة الثانية، تقع العناصر عند الفاصل الزمني 2 (n/4 = 2)، حيث n = 8.
الآن، نحن نأخذ الفاصل الزمني ل 2 لفرز بقية المصفوفة. بفاصل زمني قدره 2، سيتم إنشاء قائمتين فرعيتين - {12، 25، 33، 40}، و{17، 8، 31، 42}.
الآن، علينا مرة أخرى مقارنة القيم في كل قائمة فرعية. بعد المقارنة، يتعين علينا تبديلها إذا لزم الأمر في المصفوفة الأصلية. بعد المقارنة والتبديل، سوف تبدو المصفوفة المحدثة كما يلي -
في الحلقة الثالثة، تقع العناصر عند الفاصل الزمني 1 (n/8 = 1)، حيث n = 8. وأخيرًا، نستخدم الفاصل الزمني للقيمة 1 لفرز بقية عناصر المصفوفة. في هذه الخطوة، يستخدم فرز الصدفة الفرز بالإدراج لفرز عناصر المصفوفة.
الآن، تم ترتيب المصفوفة تصاعديًا.
تعقيد نوع شل
الآن، دعونا نرى التعقيد الزمني لفرز Shell في أفضل حالة، ومتوسطة، وأسوأ حالة. سنرى أيضًا مدى التعقيد المكاني لنوع Shell.
1. تعقيد الوقت
| قضية | تعقيد الوقت |
|---|---|
| أفضل حالة | يا (ن * تسجيل الدخول) |
| متوسط الحالة | يا (ن * سجل (ن)2) |
| الحالة الأسوأ | على2) |
2. تعقيد الفضاء
| تعقيد الفضاء | يا(1) |
| مستقر | لا |
- التعقيد المكاني لفرز Shell هو O(1).
تنفيذ نوع شل
الآن، دعونا نرى برامج شل مرتبة في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ فرز Shell بلغة 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;>