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

ضع في اعتبارك الأرقام التالية:

50 60 30 10 80 70 20 40

إذا تم فرز هذه القائمة بترتيب تصاعدي ، فستكون:

10 20 30 40 50 60 70 80

إذا تم فرزها بترتيب تنازلي ، فسيكون:

80 70 60 50 40 30 20 10

فرز الإدراج عبارة عن خوارزمية فرز تُستخدم لفرز القائمة بترتيب تصاعدي أو تنازلي. تتناول هذه المقالة الفرز بترتيب تصاعدي فقط. يتبع الفرز بترتيب تنازلي نفس المنطق الوارد في هذه الوثيقة. الهدف من هذه المقالة هو شرح نوع الإدراج. تمت البرمجة في المثال التالي في C. يتم شرح فرز الإدراج هنا باستخدام مصفوفة واحدة.

خوارزمية لفرز الإدراج

يتم إعطاء قائمة لم يتم فرزها. الهدف هو فرز القائمة بترتيب تصاعدي باستخدام نفس القائمة. يُقال أن فرز المصفوفة غير المفروزة باستخدام نفس المصفوفة يتم الفرز في المكان. يتم استخدام الفهرسة على أساس الصفر هنا. والخطوات هي كما يلي:

• • يتم فحص القائمة من البداية.
  • أثناء إجراء المسح ، يتم تبديل أي رقم أقل من سابقه مع سابقه.
  • يستمر هذا التبادل على طول القائمة ، حتى يصبح من غير الممكن التبديل.
  • عندما يصل المسح إلى النهاية ، يكون الفرز قد اكتمل.

إدراج فرز الرسم التوضيحي

عند التعامل مع تعقيد الوقت ، فإن أسوأ الحالات التي يتم أخذها في الاعتبار عادة. أسوأ ترتيب للقائمة السابقة هو:

80 70 60 50 40 30 20 10

هناك ثمانية عناصر بفهارس من صفر إلى 7.

عند الفهرس صفر ، يذهب المسح إلى 80. هذه حركة واحدة. هذه الحركة هي عملية. هناك إجمالي عملية واحدة حتى الآن (حركة واحدة ، لا مقارنة ، ولا مقايضة). النتيجه هي:

| 80 70 60 50 40 30 20 10

في المؤشر الأول ، هناك حركة إلى 70. 70 بالمقارنة مع 80. يتم تبديل 70 و 80. حركة واحدة هي عملية واحدة. مقارنة واحدة هي أيضًا عملية واحدة. المقايضة الواحدة هي أيضًا عملية واحدة. يقدم هذا القسم ثلاث عمليات. يوجد إجمالي أربع عمليات حتى الآن (1 + 3 = 4). والنتيجة هي على النحو التالي:

70 | 80 60 50 40 30 20 10

في الفهرس الثاني ، هناك حركة إلى 60. 60 مقارنة بـ 80 ، ثم يتم تبديل 60 و 80. 60 مقابل 70 ، ثم يتم تبديل 60 و 70. حركة واحدة هي عملية واحدة. مقارنتان عمليتان. اثنان من المقايضات هما عمليتان. يقدم هذا القسم خمس عمليات. يوجد إجمالي تسع عمليات حتى الآن (4 + 5 = 9). والنتيجة هي على النحو التالي:

60 70 | 80 50 40 30 20 10

في المؤشر الثالث ، هناك حركة إلى 50. يتم مقارنة 50 مع 80 ، ثم يتم تبديل 50 و 80. يتم مقارنة 50 بـ 70 ، ثم يتم تبديل 50 و 70. يتم مقارنة 50 بـ 60 ، ثم يتم تبديل 50 و 60. حركة واحدة هي عملية واحدة. ثلاث مقارنات هي ثلاث عمليات. ثلاث مقايضات هي ثلاث عمليات. يقدم هذا القسم سبع عمليات. يوجد إجمالي ستة عشر عملية حتى الآن (9 + 7 = 16). والنتيجة هي على النحو التالي:

50 60 70 | 80 40 30 20 10

في المؤشر الرابع ، هناك حركة إلى 40. 40 بالمقارنة مع 80 ، ثم يتم تبديل 40 و 80. 40 مقارنة بـ 70 ، ثم يتم تبديل 40 و 70. 40 مقارنة بـ 60 ، ثم يتم تبديل 40 و 60. 40 مقارنة بـ 50 ، ثم يتم تبديل 40 و 50. حركة واحدة هي عملية واحدة. أربع مقارنات هي أربع عمليات. أربع مقايضات هي أربع عمليات. يقدم هذا القسم تسع عمليات. هناك إجمالي 25 عملية حتى الآن (16 + 9 = 25). والنتيجة هي على النحو التالي:

40 50 60 70 80 | 30 20 10

في الفهرس الخامس ، هناك حركة إلى 30. 30 بالمقارنة مع 80 ، ثم يتم تبديل 30 و 80. 30 مقارنة بـ 70 ، ثم يتم تبديل 30 و 70. 30 مقارنة بـ 60 ، ثم يتم تبديل 30 و 60. تتم مقارنة 30 بـ 50 ، ثم يتم تبديل 30 و 50. 30 مقارنة بـ 40 ، ثم يتم تبديل 30 و 40. حركة واحدة هي عملية واحدة. خمس مقارنات خمس عمليات. خمسة مقايضات هي خمس عمليات. يقدم هذا القسم إحدى عشرة عملية. هناك إجمالي ست وثلاثين عملية حتى الآن (25 + 11 = 36). والنتيجة هي على النحو التالي:

30 40 50 60 70 80 | 20 10

في المؤشر السادس ، هناك حركة إلى 20. 20 مقارنة بـ 80 ، ثم يتم تبديل 20 و 80. 20 مقابل 70 ، ثم يتم تبديل 20 و 70. 20 مقارنة بـ 60 ، ثم يتم تبديل 20 و 60. 20 مقارنة بـ 50 ، ثم يتم تبديل 20 و 50. 20 مقارنة بـ 40 ، ثم يتم تبديل 20 و 40. 20 مقارنة بـ 30 ، ثم يتم تبديل 20 و 30. حركة واحدة هي عملية واحدة. ست مقارنات ست عمليات. ستة مقايضات هي ست عمليات. يقدم هذا القسم ثلاث عشرة عملية. هناك ما مجموعه تسعة وأربعون عملية حتى الآن (36 + 13 = 49). والنتيجة هي على النحو التالي:

20 30 40 50 60 70 80 | 10

في المؤشر السابع ، توجد حركة عند 10. يتم مقارنة 10 بـ 80 ، ثم يتم تبديل 10 و 80. يتم مقارنة 10 بـ 70 ، ثم يتم تبديل 10 و 70. يتم مقارنة 10 بـ 60 ، ثم يتم تبديل 10 و 60. يتم مقارنة 10 بـ 50 ، ثم يتم تبديل 10 و 50. يتم مقارنة 10 بـ 30 ، ثم يتم تبديل 10 و 40. يتم مقارنة 10 بـ 30 ، ثم يتم تبديل 10 و 30. يتم مقارنة 10 بـ 20 ، ثم يتم تبديل 10 و 20. حركة واحدة هي عملية واحدة. سبع مقارنات سبع عمليات. سبع مقايضات هي سبع عمليات. يقدم هذا القسم خمس عشرة عملية. هناك ما مجموعه 64 عملية حتى الآن (49 + 15 = 64). والنتيجة هي على النحو التالي:

10 20 30 40 50 60 70 80 10 |

تم إنجاز المهمة! تم إشراك 64 عملية.

64 = 8 × 8 = 8 ^اثنين

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

إذا كان هناك عناصر n للفرز باستخدام Insertion Sort ، فسيكون الحد الأقصى لعدد العمليات الممكنة n2 ، كما هو موضح سابقًا. درجة تعقيد وقت فرز الإدراج هي:

على ^اثنين )

يستخدم هذا تدوين Big-O. يبدأ تدوين Big-O بالحرف O بأحرف كبيرة ، متبوعًا بأقواس. يوجد داخل الأقواس تعبير لأقصى عدد ممكن من العمليات.

الترميز في C.

في بداية الفحص ، لا يمكن للعنصر الأول تغيير موضعه. البرنامج هو في الأساس ما يلي:

يستخدم تعريف دالة insertionSort () الخوارزمية كما هو موضح. لاحظ شروط حلقة while-loop. وظيفة C الرئيسية المناسبة لهذا البرنامج هي:

استنتاج

التعقيد الزمني لفرز الإدراج معطى على النحو التالي:

على ^اثنين )

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