في هذه المقالة، سنناقش خوارزمية الفرز بالإدراج. إجراءات العمل لفرز الإدراج بسيطة أيضًا. ستكون هذه المقالة مفيدة جدًا ومثيرة للاهتمام للطلاب حيث قد يواجهون نوع الإدراج كسؤال في امتحاناتهم. لذلك، من المهم مناقشة الموضوع.
يعمل فرز الإدراج بشكل مشابه لفرز أوراق اللعب في الأيدي. من المفترض أن البطاقة الأولى تم فرزها بالفعل في لعبة الورق، ثم نختار بطاقة غير مصنفة. إذا كانت البطاقة غير المصنفة المحددة أكبر من البطاقة الأولى، فسيتم وضعها على الجانب الأيمن؛ وإلا فسيتم وضعه على الجانب الأيسر. وبالمثل، يتم أخذ جميع البطاقات التي لم يتم فرزها ووضعها في مكانها الصحيح.
يتم تطبيق نفس الأسلوب في فرز الإدراج. الفكرة وراء فرز الإدراج هي أن نأخذ عنصرًا واحدًا أولاً، ثم نكرره من خلال المصفوفة التي تم فرزها. على الرغم من أنه سهل الاستخدام، إلا أنه غير مناسب لمجموعات البيانات الكبيرة حيث أن التعقيد الزمني لفرز الإدراج في الحالة المتوسطة والحالة الأسوأ هو على2) ، حيث n هو عدد العناصر. يعتبر فرز الإدراج أقل كفاءة من خوارزميات الفرز الأخرى مثل فرز الكومة، والفرز السريع، والفرز المدمج، وما إلى ذلك.
يتميز فرز الإدراج بمزايا مختلفة مثل -
- تنفيذ بسيط
- فعالة لمجموعات البيانات الصغيرة
- متكيف، أي أنه مناسب لمجموعات البيانات التي تم فرزها بالفعل بشكل كبير.
الآن، دعونا نرى خوارزمية فرز الإدراج.
خوارزمية
يتم سرد الخطوات البسيطة لتحقيق فرز الإدراج على النحو التالي -
الخطوة 1 - إذا كان العنصر هو العنصر الأول، فافترض أنه تم فرزه بالفعل. العودة 1.
مقارنة بالسلاسل في Java
الخطوة 2 - اختر العنصر التالي، وقم بتخزينه بشكل منفصل في ملف مفتاح.
الخطوه 3 - الآن، قارن بين مفتاح مع كافة العناصر الموجودة في المصفوفة التي تم فرزها.
الخطوة 4 - إذا كان العنصر الموجود في المصفوفة التي تم فرزها أصغر من العنصر الحالي، فانتقل إلى العنصر التالي. بخلاف ذلك، قم بنقل العناصر الأكبر في المصفوفة نحو اليمين.
الخطوة 5 - أدخل القيمة.
الخطوة 6 - كرر ذلك حتى يتم فرز المصفوفة.
عمل خوارزمية الفرز بالإدراج
الآن دعونا نرى عمل خوارزمية فرز الإدراج.
لفهم عمل خوارزمية فرز الإدراج، لنأخذ مصفوفة غير مصنفة. سيكون من الأسهل فهم نوع الإدراج من خلال مثال.
دع عناصر المصفوفة هي -
في البداية، تتم مقارنة العنصرين الأولين في نوع الإدراج.
هنا، 31 أكبر من 12. وهذا يعني أن كلا العنصرين موجودان بالفعل في ترتيب تصاعدي. لذا، في الوقت الحالي، يتم تخزين 12 في مصفوفة فرعية مرتبة.
انتقل الآن إلى العنصرين التاليين وقم بمقارنتهما.
هنا، 25 أصغر من 31. إذن، 31 ليس في موضعه الصحيح. الآن، قم بتبديل 31 بـ 25. إلى جانب المبادلة، سيتحقق فرز الإدراج أيضًا من جميع العناصر الموجودة في المصفوفة التي تم فرزها.
في الوقت الحالي، تحتوي المصفوفة التي تم فرزها على عنصر واحد فقط، أي 12. لذا، فإن 25 أكبر من 12. ومن ثم، تظل المصفوفة التي تم فرزها مرتبة بعد التبديل.
الآن، هناك عنصران في المصفوفة التي تم فرزها هما 12 و25. انتقل للأمام إلى العنصرين التاليين وهما 31 و8.
لم يتم فرز كل من 31 و 8. لذا، قم بتبديلهم.
بعد التبديل، لا يتم فرز العنصرين 25 و8.
لذا، قم بتبديلهم.
الآن، العناصر 12 و 8 غير مصنفة.
لذلك، قم باستبدالها أيضًا.
الآن، تحتوي المصفوفة التي تم فرزها على ثلاثة عناصر هي 8 و12 و25. انتقل إلى العناصر التالية وهي 31 و32.
وبالتالي، فقد تم فرزها بالفعل. الآن، تتضمن المصفوفة التي تم فرزها 8 و12 و25 و31.
انتقل إلى العنصرين التاليين وهما 32 و17.
17 أصغر من 32. لذا، قم بتبديلهما.
المبادلة تجعل 31 و 17 غير مصنفة. لذلك، قم باستبدالها أيضًا.
الآن، يؤدي التبديل إلى جعل العددين 25 و17 غير مصنفين. لذلك، قم بإجراء المبادلة مرة أخرى.
الآن، تم فرز المصفوفة بالكامل.
تعقيد فرز الإدراج
الآن، دعونا نرى التعقيد الزمني لفرز الإدراج في أفضل الأحوال، وفي المتوسط، وفي أسوأ الحالات. سنرى أيضًا التعقيد المكاني لفرز الإدراج.
1. تعقيد الوقت
| قضية | تعقيد الوقت |
|---|---|
| أفضل حالة | على) |
| متوسط الحالة | على2) |
| الحالة الأسوأ | على2) |
2. تعقيد الفضاء
| تعقيد الفضاء | يا(1) |
| مستقر | نعم |
- التعقيد المكاني لفرز الإدراج هو O(1). وذلك لأنه في عملية الفرز بالإدراج، يلزم وجود متغير إضافي للتبديل.
تنفيذ نوع الإدراج
الآن، دعونا نرى برامج الفرز بالإدراج في لغات البرمجة المختلفة.
برنامج: اكتب برنامجًا لتنفيذ فرز الإدراج في لغة C.
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> انتاج:
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.
لم تقتصر هذه المقالة على الخوارزمية فقط. لقد ناقشنا أيضًا مدى تعقيد الخوارزمية وعملها وتنفيذها بلغات برمجة مختلفة.