במאמר זה, נדון באלגוריתם מיון המעטפת. מיון מעטפת הוא הכללה של מיון הכנסה, שמתגבר על החסרונות של מיון הכנסה על ידי השוואת אלמנטים המופרדים בפער של מספר מיקומים.
זהו אלגוריתם מיון שהוא גרסה מורחבת של מיון הכנסה. מיון מעטפת שיפר את מורכבות הזמן הממוצעת של מיון ההכנסה. בדומה למיון הכנסה, זהו אלגוריתם מיון המבוסס על השוואה ובמקום. מיון מעטפת יעיל עבור מערכי נתונים בגודל בינוני.
במיון הוספה, בכל פעם, ניתן להזיז אלמנטים קדימה במיקום אחד בלבד. כדי להעביר אלמנט למיקום מרוחק, נדרשות תנועות רבות המגדילות את זמן הביצוע של האלגוריתם. אבל מיון מעטפת מתגבר על החיסרון הזה של מיון הכנסה. זה מאפשר תנועה והחלפה של אלמנטים רחוקים גם כן.
אלגוריתם זה ממיין תחילה את האלמנטים הרחוקים זה מזה, ואז הוא מקטין את הפער ביניהם. הפער הזה נקרא בשם הַפסָקָה. ניתן לחשב מרווח זה באמצעות ה- של קנוט הנוסחה המובאת להלן -
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}.
כעת, עלינו להשוות את הערכים בכל תת-רשימה. לאחר ההשוואה, עלינו להחליף אותם במידת הצורך במערך המקורי. לאחר השוואה והחלפה, המערך המעודכן ייראה כך -
בלולאה השנייה, אלמנטים שוכבים במרווח של 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. מורכבות זמן
| מקרה | מורכבות זמן |
|---|---|
| המקרה הטוב ביותר | O(n*logn) |
| מקרה ממוצע | O(n*log(n)2) |
| במקרה הגרוע ביותר | עַל2) |
2. מורכבות החלל
| מורכבות החלל | O(1) |
| יַצִיב | לא |
- מורכבות החלל של מיון מעטפת היא O(1).
יישום של מיון Shell
כעת, בואו נראה את התוכניות של Shell ממוינות בשפות תכנות שונות.
תכנית: כתוב תוכנית ליישום מיון 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;>