- جائزہ
- جنرل الگورتھم
- سیوڈو کوڈ
- مثال
- C++ مثال
- Java Example
- Complexity Analysis Of The Insertion Sort Algorithm
- Conclusion
کلاسیکی مثالوں کے ساتھ اندراج کی ترتیب پر گہرائی سے نظر ڈالیں۔
انسرشن ترتیب چھانٹنے کی ایک تکنیک ہے جسے اس طرح دیکھا جاسکتا ہے جس طرح ہم ہاتھ میں تاش کھیلتے ہیں۔ جس طرح سے ہم کسی بھی کارڈ کو ڈیک میں داخل کرتے ہیں یا اسے ہٹاتے ہیں، اندراج کی ترتیب اسی طرح کام کرتی ہے۔
انسرشن کی ترتیب الگورتھم تکنیک ببل کی ترتیب اور سلیکشن کی ترتیب کی تکنیک سے زیادہ موثر ہے لیکن دوسری تکنیکوں سے کم موثر ہے۔ جیسے Quicksort اور Merge sort.
جائزہ
انسرشن ترتیب کی تکنیک میں، ہم دوسرے عنصر سے شروع کرتے ہیں اور اس کا پہلے عنصر سے موازنہ کرتے ہیں اور اسے ڈالتے ہیں۔ ایک مناسب جگہ پر. پھر ہم اس عمل کو بعد کے عناصر کے لیے انجام دیتے ہیں۔
ہم ہر عنصر کا اس کے تمام سابقہ عناصر سے موازنہ کرتے ہیں اور عنصر کو اس کی مناسب پوزیشن میں رکھتے یا داخل کرتے ہیں۔ اندراج کی ترتیب کی تکنیک عناصر کی کم تعداد والی صفوں کے لیے زیادہ قابل عمل ہے۔ یہ لنک شدہ فہرستوں کو چھانٹنے کے لیے بھی مفید ہے۔
لنک شدہ فہرستوں میں اگلے عنصر کی طرف ایک پوائنٹر ہوتا ہے (اکیلی لنک کی گئی فہرست کی صورت میں) اور پچھلے عنصر کی طرف بھی ایک پوائنٹر ہوتا ہے (دوگنا منسلک فہرست کی صورت میں )۔ اس لیے لنک شدہ فہرست کے لیے اندراج کی ترتیب کو لاگو کرنا آسان ہو جاتا ہے۔
آئیے اس ٹیوٹوریل میں اندراج کی ترتیب کے بارے میں سب کچھ دریافت کریں۔
جنرل الگورتھم
مرحلہ 1 : K = 1 سے N-1 کے لیے 2 سے 5 مراحل کو دہرائیں
مرحلہ 2 : سیٹ temp = A[K]
مرحلہ 3 : سیٹ کریں J = K– 1
مرحلہ 4 : دہرائیں جب کہ temp =A[J]
سیٹ A[J + 1] = A[J]
سیٹ J = J – 1
[اندرونی لوپ کا اختتام]
مرحلہ 5 : سیٹ کریں A[J + 1] = temp
[ لوپ کا اختتام]
مرحلہ 6 : باہر نکلیں
اس طرح، داخل کرنے کی ترتیب کی تکنیک میں، ہم دوسرے عنصر سے شروع کرتے ہیں جیسا کہ ہم فرض کرتے ہیں کہ پہلا عنصر ہمیشہ ترتیب دیا جاتا ہے۔ . پھر دوسرے عنصر سے لے کر آخری عنصر تک، ہم ہر عنصر کا اس کے تمام پچھلے عناصر سے موازنہ کرتے ہیں اور اس عنصر کو مناسب پوزیشن میں رکھتے ہیں۔
سیوڈو کوڈ
اندراج کی ترتیب ذیل میں دی گئی ہے۔
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1] >insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure
اوپر دیا گیا ہے داخل کرنے کی ترتیب کے لیے چھدم کوڈ، اگلا، ہم اس تکنیک کو درج ذیل مثال میں واضح کریں گے۔
مثال
0 ترتیب کی جانے والی صف درج ذیل ہے: 
اب ہر پاس کے لیے، ہم موجودہ عنصر کا اس کے پچھلے تمام عناصر سے موازنہ کرتے ہیں۔ لہذا پہلے پاس میں، ہم دوسرے عنصر کے ساتھ شروع کرتے ہیں۔
اس طرح ہمیں عناصر کی N تعداد والی صف کو مکمل طور پر ترتیب دینے کے لیے پاسز کی تعداد درکار ہوتی ہے۔
مذکورہ بالا مثال کا خلاصہ ٹیبلر شکل میں کیا جا سکتا ہے:
| پاس | غیر ترتیب شدہ فہرست | موازنہ | ترتیب دیا گیا۔فہرست |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12,3} | {3,12,5,10,8,1} |
| 2 | {3,12,5,10,8,1}17 | {3,12,5} | {3,5,12,10,8,1} |
| 3 | { 3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
جیسا کہ اس میں دکھایا گیا ہے اوپر کی مثال، ہم دوسرے عنصر سے شروع کرتے ہیں جیسا کہ ہم فرض کرتے ہیں کہ پہلا عنصر ہمیشہ ترتیب دیا جاتا ہے۔ اس لیے ہم دوسرے عنصر کا پہلے سے موازنہ کرنے کے ساتھ شروع کرتے ہیں اور اگر دوسرا عنصر پہلے سے کم ہو تو پوزیشن کو تبدیل کرتے ہیں۔
یہ موازنہ اور تبدیل کرنے کا عمل دو عناصر کو ان کی مناسب جگہوں پر رکھتا ہے۔ اس کے بعد، ہم تیسرے عنصر کا اس کے پچھلے (پہلے اور دوسرے) عناصر سے موازنہ کرتے ہیں اور تیسرے عنصر کو مناسب جگہ پر رکھنے کے لیے وہی طریقہ کار انجام دیتے ہیں۔
اس طریقے سے، ہر پاس کے لیے، ہم ایک عنصر کو اس میں رکھتے ہیں۔ اس کی جگہ. پہلے پاس کے لیے، ہم دوسرے عنصر کو اس کی جگہ پر رکھتے ہیں۔ اس طرح عام طور پر، N عناصر کو ان کی مناسب جگہ پر رکھنے کے لیے، ہمیں N-1 پاسز کی ضرورت ہے۔
اس کے بعد، ہم C++ زبان میں انسرشن ترتیب کی تکنیک کے نفاذ کا مظاہرہ کریں گے۔
C++ مثال
#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout"\nInput list is \n"; for(int i=0;i10;i++) { cout ="" Output:
Input list is
12 4 3 1 15 45 33 21 10 2
Sorted list is
1 2 3 4 10 12 15 21 33 45
Next, we will see the Java implementation of the Insertion sort technique.
Java Example
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Input list of elements ..."); for(int i=0;i10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp = myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\nsorted list of elements ..."); for(int i=0;i10;i++) { System.out.print(myarray[i] + " "); } } } Output:
Input list of elements …
12 4 3 1 15 45 33 21 10 2
sorted list of elements …
1 2 3 4 10 12 15 21 33 45
In both the implementations, we can see that we begin sorting from the 2nd element of the array (loop variable j = 1) and repeatedly compare the current element to all its previous elements and then sort the element to place it in its correct position if the current element is not in order with all its previous elements.
Insertion sort works the best and can be completed in fewer passes if the array is partially sorted. But as the list grows bigger, its performance decreases. Another advantage of Insertion sort is that it is a Stable sort which means it maintains the order of equal elements in the list.
Complexity Analysis Of The Insertion Sort Algorithm
From the pseudo code and the illustration above, insertion sort is the efficient algorithm when compared to bubble sort or selection sort. Instead of using for loop and present conditions, it uses a while loop that does not perform any more extra steps when the array is sorted.
However, even if we pass the sorted array to the Insertion sort technique, it will still execute the outer for loop thereby requiring n number of steps to sort an already sorted array. This makes the best time complexity of insertion sort a linear function of N where N is the number of elements in the array.
Thus the various complexities for Insertion sort technique are given below:
Worst case time complexity O(n 2 ) Best case time complexity O(n) Average time complexity O(n 2 ) Space complexity O(1)
In spite of these complexities, we can still conclude that Insertion sort is the most efficient algorithm when compared with the other sorting techniques like Bubble sort and Selection sort.
Conclusion
Insertion sort is the most efficient of all the three techniques discussed so far. Here, we assume that the first element is sorted and then repeatedly compare every element to all its previous elements and then place the current element in its correct position in the array.
In this tutorial, while discussing Insertion sort we have noticed that we compare the elements using an increment of 1 and also they are contiguous. This feature results in requiring more passes to get the sorted list.
In our upcoming tutorial, we will discuss “Shell sort” which is an improvement over the Selection sort.
In shell sort, we introduce a variable known as “increment” or a “gap” using which we divide the list into sublists containing non-contiguous elements that “gap” apart. Shell sort requires fewer passes when compared to Insertion sort and is also faster.
In our future tutorials, we will learn about two sorting techniques, “Quicksort” and “Mergesort” which use “Divide and conquer” strategy for sorting data lists.