TechCodeview

[ 1، 4، 10، 25 ، 25] ضع درجة الحرارة = 5

الآن، نحصل على المصفوفة التي تم فرزها ببساطة عن طريق وضع القيمة المؤقتة.

[1، 4، 5، 10، 25]

يتم فرز المصفوفة المحددة.

تطبيق

تنفيذ الإدراج سهل نسبيا. سوف نقوم بالتنفيذ باستخدام مجموعة بايثون من الأعداد الصحيحة. دعونا نفهم المثال التالي -

برنامج بايثون

 # creating a function for insertion def insertion_sort(list1): # Outer loop to traverse through 1 to len(list1) for i in range(1, len(list1)): value = list1[i] # Move elements of list1[0..i-1], that are # greater than value, to one position ahead # of their current position j = i - 1 while j &gt;= 0 and value <list1[j]: list1[j + 1]="list1[j]" j -="1" return list1 # driver code to test above 5, 13, 8, 2] print('the unsorted list is:', list1) sorted insertion_sort(list1)) < pre> <p> <strong>Output:</strong> </p> <pre> The unsorted list is: [10, 5, 13, 8, 2] The sorted list1 is: [2, 5, 8, 10, 13] </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code, we have created a function called <strong>insertion_sort(list1).</strong> Inside the function -</p> <ul> <li>We defined for loop for traverse the list from 1 to <strong>len(list1).</strong> </li> <li>In for loop, assigned a values of list1 in <strong>value</strong> Every time the loop will iterate the new value will assign to the value variable.</li> <li>Next, we moved the elements of list1[0&#x2026;i-1], that are greater than the <strong>value,</strong> to one position ahead of their current position.</li> <li>Now, we used the while to check whether the j is greater or equal than 0, and the <strong>value</strong> is smaller than the first element of the list.</li> <li>If both conditions are true then move the first element to the 0<sup>th</sup> index and reduce the value of j and so on.</li> <li>After that, we called the function and passed the list and printed the result.</li> </ul> <h2>Sorting Custom Objects</h2> <p>Python provides the flexibility to change the algorithm using a custom object. We will create a custom class and redefine the actual comparison parameter and try to keep the same code as the above.</p> <p>We would require to overload the operators in order to sort the objects in a different way. But, we can pass another argument to the <strong>insertion_sort()</strong> function by using the <strong>lambda</strong> function. The lambda function is a convenient when calling the sorting method.</p> <p>Let&apos;s understand the following example of sorting custom objects.</p> <p>First, we are defining the <strong>Point</strong> class:</p> <h3>Python Program</h3> <pre> # Creating Point class class Point: def __init__(self, a, b): self.a = a self.b = b def __str__(self): return str.format(&apos;({},{})&apos;, self.a, self.b) def insertion_sort(list1, compare_function): for i in range(1, len(list1)): Value = list1[i] Position = i while Position &gt; 0 and compare_function(list1[Position - 1], Value): list1[Position] = list1[Position - 1] Position = Position - 1 list1[Position] = Value U = Point(2,3) V = Point(4,4) X = Point(3,1) Y = Point(8,0) Z = Point(5,2) list1 = [U,V,X,Y,Z] # We sort by the x coordinate, ascending insertion_sort(list1, lambda x, y: x.a &gt; y.a) for point in list1: print(point) </pre> <p> <strong>Output:</strong> </p> <pre> The points are in the sorted order (2,3) (3,1) (4,4) (5,2) (8,0) </pre> <p>Using the above code, we can sort the coordinate points. It will work for any type of the list.</p> <h2>Time Complexity in Insertion Sort</h2> <p>Insertion sort is a slow algorithm; sometimes, it seems too slow for extensive dataset. However, it is efficient for small lists or array.</p> <p>The time complexity of the insertion sort is - <strong>O(n<sup>2</sup>).</strong> It uses the two loops for iteration.</p> <p>Another important advantage of the insertion sort is that; it is used by the popular sorting algorithm called <strong>Shell sort.</strong> </p> <p>The auxiliary space in insertion sort: <strong>O(1)</strong> </p> <h2>Conclusion</h2> <p>Insertion sort is a simple and inefficient algorithm that has many advantages, but there are more efficient algorithms are available.</p> <p>In this tutorial, we have discussed the concept of the insertion sort and its implementation using the Python programming language.</p> <hr></list1[j]:>

توضيح:

في الكود أعلاه، قمنا بإنشاء وظيفة تسمى Insertion_sort(list1). داخل الدالة -

• لقد حددنا حلقة for لاجتياز القائمة من 1 إلى لين (القائمة 1).
• في الحلقة، تم تعيين قيم list1 in قيمة في كل مرة يتم تكرار الحلقة، سيتم تعيين القيمة الجديدة لمتغير القيمة.
• بعد ذلك، قمنا بنقل عناصر القائمة1[0...i-1]، التي تكون أكبر من قيمة، إلى منصب واحد قبل وضعهم الحالي.
• الآن، استخدمنا while للتحقق مما إذا كان j أكبر أو يساوي 0، و قيمة أصغر من العنصر الأول في القائمة.
• إذا كان كلا الشرطين صحيحا، فقم بنقل العنصر الأول إلى 0^ذفهرس وتقليل قيمة j وما إلى ذلك.
• بعد ذلك قمنا باستدعاء الدالة ومررنا القائمة وطبعنا النتيجة.

فرز الكائنات المخصصة

توفر Python المرونة اللازمة لتغيير الخوارزمية باستخدام كائن مخصص. سنقوم بإنشاء فئة مخصصة وإعادة تعريف معلمة المقارنة الفعلية ومحاولة الاحتفاظ بنفس الكود المذكور أعلاه.

سنحتاج إلى زيادة التحميل على المشغلين لفرز الكائنات بطريقة مختلفة. لكن يمكننا تمرير حجة أخرى إلى ترتيب بالإدراج() وظيفة باستخدام لامدا وظيفة. تعتبر وظيفة لامدا ملائمة عند استدعاء طريقة الفرز.

رقم الأبجدية

دعونا نفهم المثال التالي لفرز الكائنات المخصصة.

أولا نقوم بتعريف نقطة فصل:

برنامج بايثون

 # Creating Point class class Point: def __init__(self, a, b): self.a = a self.b = b def __str__(self): return str.format('({},{})', self.a, self.b) def insertion_sort(list1, compare_function): for i in range(1, len(list1)): Value = list1[i] Position = i while Position > 0 and compare_function(list1[Position - 1], Value): list1[Position] = list1[Position - 1] Position = Position - 1 list1[Position] = Value U = Point(2,3) V = Point(4,4) X = Point(3,1) Y = Point(8,0) Z = Point(5,2) list1 = [U,V,X,Y,Z] # We sort by the x coordinate, ascending insertion_sort(list1, lambda x, y: x.a > y.a) for point in list1: print(point) 

انتاج:

 The points are in the sorted order (2,3) (3,1) (4,4) (5,2) (8,0) 

باستخدام الكود أعلاه، يمكننا فرز نقاط الإحداثيات. ستعمل مع أي نوع من القائمة.

تعقيد الوقت في فرز الإدراج

يعد فرز الإدراج خوارزمية بطيئة؛ في بعض الأحيان، يبدو الأمر بطيئًا جدًا بالنسبة لمجموعة البيانات الشاملة. ومع ذلك، فهو فعال للقوائم الصغيرة أو المصفوفات.

التعقيد الزمني لفرز الإدراج هو - على²). يستخدم الحلقتين للتكرار.

ميزة أخرى مهمة لفرز الإدراج هي أنه؛ يتم استخدامه بواسطة خوارزمية الفرز الشائعة التي تسمى نوع شل.

المساحة المساعدة في فرز الإدراج: يا(1)

خاتمة

يعد فرز الإدراج خوارزمية بسيطة وغير فعالة ولها العديد من المزايا، ولكن تتوفر خوارزميات أكثر كفاءة.

في هذا البرنامج التعليمي، ناقشنا مفهوم فرز الإدراج وتنفيذه باستخدام لغة البرمجة بايثون.