فرز الإدراج

فرز الإدراج هو خوارزمية فرز بسيطة تُنشئ المصفوفة (أو القائمة) النهائية المرتبة عنصرًا تلو الآخر عن طريق المقارنات . وهي أقل كفاءة بكثير على القوائم الكبيرة مقارنةً بالخوارزميات الأكثر تطورًا مثل الفرز السريع ، وفرز الكومة ، وفرز الدمج . ومع ذلك، يوفر فرز الإدراج العديد من المزايا:

• التنفيذ البسيط: يعرض جون بنتلي نسخة تتكون من ثلاثة أسطر بلغة تشبه لغة C ، وخمسة أسطر عند تحسينها . ^{[ 1 ]}
• فعالة مع مجموعات البيانات الصغيرة (إلى حد ما)، تمامًا مثل خوارزميات الفرز التربيعية الأخرى (أي O ( n² ⁾ ).
• قد يكون أكثر كفاءة من الناحية العملية من معظم الخوارزميات التربيعية البسيطة الأخرى مثل فرز التحديد أو فرز الفقاعات - ولكن ترتيب البيانات الواردة النسبي وتكاليف القراءة / الكتابة مهمة - مع ارتفاع تكاليف التبادل والبيانات المرتبة عشوائيًا، يكون فرز التحديد أسرع ^{[ 2 ].}
• تكيفي ، أي فعال لمجموعات البيانات المرتبة بشكل كبير بالفعل: التعقيد الزمني هو O ( kn ) عندما لا يزيد بُعد كل عنصر في المدخلات عن k موضعًا عن موضعه المرتب
• ثابت ؛ أي أنه لا يغير الترتيب النسبي للعناصر ذات المفاتيح المتساوية.
• في مكانها ؛ أي أنها تتطلب فقط مقدارًا ثابتًا O(1) من مساحة الذاكرة الإضافية
• متصل بالإنترنت ؛ أي أنه يستطيع فرز القائمة فور استلامها.

عندما يقوم اللاعبون بفرز البطاقات يدويًا في يد لعبة البريدج ، فإن معظمهم يستخدمون طريقة مشابهة لفرز الإدخال. ^{[ 3 ]}

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

تُجرى عملية الفرز عادةً في مكانها، وذلك بالتكرار تصاعديًا في المصفوفة، مع زيادة القائمة المُفرزة خلفها. عند كل موضع في المصفوفة، يتم التحقق من القيمة الموجودة فيه مقابل أكبر قيمة في القائمة المُفرزة (والتي تصادف أنها مجاورة لها، في الموضع السابق الذي تم التحقق منه). إذا كانت القيمة أكبر، يُترك العنصر في مكانه وينتقل إلى العنصر التالي. أما إذا كانت أصغر، فيتم البحث عن الموضع الصحيح داخل القائمة المُفرزة، ثم تُزاح جميع القيم الأكبر لأعلى لإفساح المجال، ويُدرج العنصر في ذلك الموضع الصحيح.

تتميز المصفوفة الناتجة بعد k تكرارًا بخاصية ترتيب أول k + 1 عنصرًا ("+1" لأن العنصر الأول يُحذف). في كل تكرار، يُحذف أول عنصر متبقٍ من المدخلات، ويُضاف إلى النتيجة في الموضع الصحيح، مما يؤدي إلى توسيع النتيجة.

يصبح

مع نسخ كل عنصر أكبر من x إلى اليمين أثناء مقارنته بـ x .

يمكن وصف أكثر أنواع فرز الإدراج شيوعًا، والذي يعمل على المصفوفات، على النحو التالي:

1. لنفترض وجود دالة تُسمى Insert مصممة لإدراج قيمة في تسلسل مُرتب في بداية مصفوفة. تعمل هذه الدالة بالبدء من نهاية التسلسل، حيث تُزيح كل عنصر خانة واحدة إلى اليمين حتى يتم العثور على موضع مناسب للعنصر الجديد. وتؤدي هذه الدالة إلى استبدال القيمة المخزنة مباشرةً بعد التسلسل المُرتب في المصفوفة.
2. لإجراء عملية فرز بالإدراج، ابدأ من العنصر الأيسر في المصفوفة، ثم استدعِ الدالة Insert لإدراج كل عنصر في موضعه الصحيح. يُخزَّن الترتيب الذي أُدرج فيه العنصر في بداية المصفوفة ضمن مجموعة الفهارس التي تم فحصها مسبقًا. كل عملية إدراج تستبدل قيمة واحدة فقط: القيمة التي يتم إدراجها.

فيما يلي الشفرة الزائفة للخوارزمية الكاملة، حيث تكون المصفوفات تبدأ من الصفر : ^{[ 1 ]}

i ← 1 بينما i < طول(A) j ← i بينما j > 0 و A[j-1] > A[j] قم بتبديل A[j] و A[j-1] j ← j - 1 نهاية الحلقة i ← i + 1 نهاية الحلقة

تُنفَّذ الحلقة الخارجية على جميع العناصر باستثناء العنصر الأول، لأن البادئة المكونة من عنصر واحد A[0:1]مُرتبة بشكل بديهي، وبالتالي فإن الشرط الثابت بأن العناصر الأولى iمُرتبة صحيح منذ البداية. تنقل الحلقة الداخلية العنصر A[i]إلى مكانه الصحيح بحيث i+1تكون العناصر الأولى مُرتبة بعد انتهاء الحلقة. لاحظ أن andعامل التشغيل في الاختبار يجب أن يستخدم تقييم الدائرة المختصرة ، وإلا فقد ينتج عن الاختبار خطأ في حدود المصفوفة ، عندما j=0يحاول التقييم A[j-1] > A[j](أي A[-1]فشل الوصول).

بعد توسيع swapالعملية في مكانها كـ x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(حيث xيكون متغيرًا مؤقتًا )، يمكن إنتاج نسخة أسرع قليلاً تنتقل A[i]إلى موضعها في خطوة واحدة وتنفذ عملية تعيين واحدة فقط في جسم الحلقة الداخلية: ^{[ 1 ]}

i ← 1 بينما i < طول(A) x ← A[i] j ← i بينما j > 0 و A[j-1] > x A[j] ← A[j-1] j ← j - 1 end while A[j] ← x [ 4 ] i ← i + 1 نهاية الحلقة

تقوم الحلقة الداخلية الجديدة بتحريك العناصر إلى اليمين لإفساح المجال لـ x = A[i].

يمكن أيضًا تنفيذ الخوارزمية بطريقة تكرارية. يستبدل التكرار الحلقة الخارجية، حيث يستدعي نفسه ويخزن قيمًا أصغر تدريجيًا لـ n على المكدس حتى تصبح n تساوي صفرًا، وعندها تعود الدالة إلى أعلى سلسلة الاستدعاءات لتنفيذ الكود بعد كل استدعاء تكراري بدءًا من n تساوي 1، مع زيادة n بمقدار 1 مع كل استدعاء للدالة يعود إلى الاستدعاء السابق. سيكون الاستدعاء الأولي هو insertionSortR(A, length(A)-1)...

دالة insertionSortR(المصفوفة A، العدد الصحيح n) إذا كان n > 0 insertionSortR(A, n-1) x ← A[n] j ← n-1 بينما j >= 0 و A[j] > x A[j+1] ← A[j] j ← j-1 نهاية الحلقة A[j+1] ← x نهاية الشرط نهاية الدالة

لا يؤدي ذلك إلى تقصير الكود، كما أنه لا يقلل من وقت التنفيذ، ولكنه يزيد من استهلاك الذاكرة الإضافي من O(1) إلى O(N) (في أعمق مستوى من الاستدعاء الذاتي، يحتوي المكدس على N مرجعًا للمصفوفة A، كل منها مصحوب بقيمة متغير nمن N إلى 1).

فيما يلي تطبيق مكتوب بلغة C.

// ترتب المصفوفة تصاعديًا باستخدام خوارزمية فرز الإدراج. void insertionSort ( int a [], int n ) { // نعتبر a[0..i-1] الجزء المرتب، و a[i..end] الجزء غير المرتب. for ( int i = 1 ; i < n ; i ++ ) { int key = a [ i ]; // القيمة التي نريد إدراجها في الجزء المرتب. int j = i - 1 ;// إزاحة العناصر الأكبر حجمًا موضعًا واحدًا إلى اليمين // حتى نجد مكان 'key'. while ( j >= 0 && a [ j ] > key ) { a [ j + 1 ] = a [ j ]; j -- ; }// ضع المفتاح 'key' في الفراغ الناتج عن عملية الإزاحة. a [ j + 1 ] = key ; } }

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

أبسط مدخل في أسوأ الحالات هو مصفوفة مرتبة ترتيبًا عكسيًا. تتكون مجموعة جميع المدخلات في أسوأ الحالات من جميع المصفوفات التي يكون فيها كل عنصر هو الأصغر أو ثاني أصغر عنصر من العناصر التي تسبقه. في هذه الحالات، تقوم كل دورة من دورات الحلقة الداخلية بمسح وإزاحة الجزء الفرعي المرتب بالكامل من المصفوفة قبل إدراج العنصر التالي. هذا يجعل وقت تشغيل فرز الإدراج تربيعيًا (أي O( n² ⁾ ).

في الحالة المتوسطة، يكون الترتيب تربيعيًا أيضًا، ^{[ 5 ]} مما يجعل فرز الإدراج غير عملي لفرز المصفوفات الكبيرة. مع ذلك، يُعد فرز الإدراج من أسرع الخوارزميات لفرز المصفوفات الصغيرة جدًا، حتى أنه أسرع من الفرز السريع ؛ في الواقع، تستخدم تطبيقات الفرز السريع الجيدة فرز الإدراج للمصفوفات الأصغر من عتبة معينة، حتى عند ظهورها كمسائل فرعية؛ يجب تحديد العتبة بدقة تجريبيًا وتعتمد على الجهاز، ولكنها عادةً ما تكون حوالي عشرة.

مثال: يوضح الجدول التالي خطوات فرز التسلسل {3، 7، 4، 9، 5، 2، 6، 1}. في كل خطوة، يُوضع خط تحت المفتاح قيد الدراسة. أما المفتاح الذي نُقل (أو تُرك في مكانه لأنه كان الأكبر حتى الآن) في الخطوة السابقة، فيُشار إليه بعلامة نجمة.

3 7 4 9 5 2 6 1 3* 7 4 9 5 2 6 1 3 7* 4 9 5 2 6 1 3 4* 7 9 5 2 6 1 3 4 7 9* 5 2 6 1 3 4 5* 7 9 2 6 1 2* 3 4 5 7 9 6 1 2 3 4 5 6* 7 9 1 1* 2 3 4 5 6 7 9

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

تتمثل الميزة الأساسية لفرز الإدراج على فرز الاختيار في أن فرز الاختيار يتطلب دائمًا فحص جميع العناصر المتبقية للعثور على أصغر عنصر في الجزء غير المرتب من القائمة، بينما يتطلب فرز الإدراج مقارنة واحدة فقط عندما يكون العنصر ( k + 1) أكبر من العنصر k . وعندما يكون هذا صحيحًا في أغلب الأحيان (كما لو كانت مصفوفة الإدخال مرتبة بالفعل أو مرتبة جزئيًا)، يكون فرز الإدراج أكثر كفاءة بشكل ملحوظ مقارنةً بفرز الاختيار. في المتوسط ​​(بافتراض أن رتبة العنصر ( k + 1) عشوائية)، سيتطلب فرز الإدراج مقارنة وإزاحة نصف العناصر k السابقة ، مما يعني أن فرز الإدراج سيجري نصف عدد المقارنات التي يجريها فرز الاختيار في المتوسط.

في أسوأ الحالات لفرز الإدراج (عندما تكون مصفوفة الإدخال معكوسة الترتيب)، يُجري فرز الإدراج نفس عدد المقارنات التي يُجريها فرز التحديد. مع ذلك، من عيوب فرز الإدراج مقارنةً بفرز التحديد أنه يتطلب عمليات كتابة أكثر، وذلك لأن إدراج العنصر ( k + 1) في الجزء المُرتب من المصفوفة في كل تكرار يتطلب العديد من عمليات تبديل العناصر لإزاحة جميع العناصر التالية، بينما يتطلب فرز التحديد عملية تبديل واحدة فقط في كل تكرار. عمومًا، يكتب فرز الإدراج إلى المصفوفة O( n² ) مرة، بينما يكتب فرز التحديد O( n ) مرة فقط. لهذا السبب ^، قد يكون فرز التحديد مُفضلاً في الحالات التي تكون فيها الكتابة إلى الذاكرة أكثر تكلفة بكثير من القراءة، كما هو الحال مع ذاكرة EEPROM أو ذاكرة الفلاش .

بينما تتفوق بعض خوارزميات فرق تسد، مثل الفرز السريع والفرز بالدمج، على فرز الإدراج في حالة المصفوفات الكبيرة، فإن خوارزميات الفرز غير التكرارية، مثل فرز الإدراج أو فرز التحديد، تكون أسرع عمومًا في حالة المصفوفات الصغيرة جدًا (يختلف الحجم الدقيق باختلاف البيئة والتنفيذ، ولكنه يتراوح عادةً بين 7 و50 عنصرًا). لذلك، يُعدّ استخدام خوارزمية هجينة، تعتمد على الخوارزمية الأبسط عند تقسيم المصفوفة إلى حجم صغير، تحسينًا مفيدًا في تنفيذ هذه الخوارزميات. ^{[ 1 ]}

أدخلت لغة DL Shell تحسينات جوهرية على الخوارزمية؛ وتُسمى النسخة المُعدّلة منها فرز شل . تُقارن خوارزمية الفرز العناصر التي تفصل بينها مسافة تتناقص في كل دورة. وقد حسّن فرز شل أوقات التشغيل بشكل ملحوظ في التطبيقات العملية، حيث يتطلب نوعان بسيطان منه وقت تشغيل قدره O( n³ ^/² ) و O( n⁴ ^/³ ) على التوالي. ^{[ 6 ] [ 7 ]}

إذا تجاوزت تكلفة المقارنات تكلفة عمليات التبديل، كما هو الحال مثلاً مع مفاتيح السلاسل المخزنة بالمرجع أو مع التفاعل البشري (مثل اختيار عنصر واحد من زوج معروض جنبًا إلى جنب)، فقد يُحسّن استخدام فرز الإدراج الثنائي الأداء. ^{[ 8 ]} يستخدم فرز الإدراج الثنائي بحثًا ثنائيًا لتحديد الموقع الصحيح لإدراج العناصر الجديدة، وبالتالي يُجري ⌈log ₂ n ⌉ مقارنة في أسوأ الحالات. عند البحث عن كل عنصر في المصفوفة وإدراجه، يكون زمن العملية O( n log n ) . ^{[ 8 ]} مع ذلك، يظل زمن تشغيل الخوارزمية ككل O( n ² ) في المتوسط ​​بسبب سلسلة عمليات التبديل المطلوبة لكل عملية إدراج. ^{[ 8 ]}

يمكن تقليل عدد عمليات التبديل بحساب موضع عدة عناصر قبل نقلها. على سبيل المثال، إذا تم حساب الموضع المستهدف لعنصرين قبل نقلهما إلى الموضع الصحيح، يمكن تقليل عدد عمليات التبديل بنسبة 25% تقريبًا للبيانات العشوائية. في الحالات القصوى، يعمل هذا الأسلوب بشكل مشابه لفرز الدمج .

يستخدم نوعٌ مُعدّل يُسمى فرز الدمج الثنائي فرز الإدراج الثنائي لفرز مجموعات من 32 عنصرًا، يليه فرز نهائي باستخدام فرز الدمج . وهو يجمع بين سرعة فرز الإدراج على مجموعات البيانات الصغيرة وسرعة فرز الدمج على مجموعات البيانات الكبيرة. ^{[ 9 ]}

لتجنب إجراء سلسلة من عمليات التبديل لكل عملية إدخال، يمكن تخزين المدخلات في قائمة مرتبطة ، مما يسمح بإضافة العناصر إلى القائمة أو إزالتها منها في وقت ثابت عندما يكون موقع العنصر في القائمة معروفًا. مع ذلك، يتطلب البحث في قائمة مرتبطة تتبع الروابط من كل عنصر إلى العنصر التالي (أو السابق) بشكل متسلسل: فالقائمة المرتبطة لا تدعم الوصول العشوائي ، لذا لا يمكنها استخدام طريقة أسرع مثل البحث الثنائي للعثور ^على نقطة إدخال عنصر غير مُرتب. لذلك، فإن وقت التشغيل المطلوب للبحث هو O( n )، ووقت الترتيب هو O( n² ). إذا تم استخدام بنية بيانات أكثر تطورًا (مثل الكومة أو الشجرة الثنائية )، يمكن تقليل الوقت المطلوب للبحث والإدخال بشكل كبير؛ وهذا هو جوهر فرز الكومة وفرز الشجرة الثنائية .

في عام 2006، نشر كلٌّ من بيندر ومارتن فاراش-كولتون وموستيرو نوعًا جديدًا من خوارزمية فرز الإدراج يُسمى فرز المكتبة أو فرز الإدراج ذي الفجوات ، والذي يترك عددًا قليلًا من المساحات غير المستخدمة (أي "الفجوات") موزعة في جميع أنحاء المصفوفة. وتكمن فائدة هذه الخوارزمية في أن عمليات الإدراج لا تتطلب سوى تحريك العناصر حتى الوصول إلى فجوة. وقد أظهر الباحثون أن خوارزمية الفرز هذه تعمل باحتمالية عالية في زمن قدره O( n log n ) . ^{[ 10 ]}

في حال استخدام قائمة التخطي ، ينخفض ​​زمن الإضافة إلى O(log n ) ، ولا حاجة لعمليات التبديل لأن قائمة التخطي مُنفذة على بنية قائمة مرتبطة. ويكون زمن التشغيل النهائي للإضافة O( n log n ) .

struct LinkedList { int value ; struct LinkedList * next ; };struct LinkedList * sortList ( struct LinkedList * list ) { // صفر أو عنصر واحد في القائمة if ( list == NULL || list -> next == NULL ) { return list ; } // head هو العنصر الأول في القائمة المرتبة الناتجة struct LinkedList * head = NULL ; while ( list != NULL ) { struct LinkedList * current = list ; list = list -> next ; if ( head == NULL || current -> value < head -> value ) { // إدراج العنصر في رأس القائمة المرتبة // أو كأول عنصر في قائمة مرتبة فارغة current -> next = head ; head = current ; } else { // إدراج العنصر الحالي في الموضع الصحيح في قائمة مرتبة غير فارغة struct LinkedList * p = head ; بينما ( p != NULL ) { // تحقق من العنصر الأخير في القائمة المرتبة ووسط القائمة إذا ( p- > next == NULL || current- > value < p- > next- > value ) { // أدرج في وسط القائمة المرتبة أو كآخر عنصر current- > next = p- > next ; p- > next = current ; break ; // تم } p = p- > next ; } } } return head ; }

struct LinkedList * sortList ( struct LinkedList * list ) { // صفر أو عنصر واحد في القائمة if ( list == NULL || list -> next == NULL ) { return list ; }// بناء المصفوفة المرتبة من قائمة فارغة struct LinkedList * sorted = NULL ;// إزالة العناصر من قائمة الإدخال واحدًا تلو الآخر حتى تصبح فارغة while ( list != NULL ) { // تذكر رأس القائمة struct LinkedList * head = list ; // مؤشر النهاية لعملية دمج فعالة struct LinkedList ** trail = & sorted ;// إزالة رأس القائمة list = list -> next ;// أضف العنصر 'head' إلى القائمة المرتبة في المكان المناسب // هل ينتمي العنصر 'head' إلى هنا؟ while ( ! ( * trail == NULL || head -> value < ( * trail ) -> value )) { // لا - تابع إلى أسفل القائمة trail = & ( * trail ) -> next ; }head -> next = * trail ; * trail = head ; }أعد الترتيب ; }

• كنوت، دونالد (1998)، "5.2.1: الفرز بالإدراج"، فن برمجة الحاسوب ، المجلد  3. الفرز والبحث (  الطبعة الثانية)، أديسون-ويسلي، الصفحات 80-105 ، ISBN  0-201-89685-0.

• خوارزميات الفرز المتحركة: فرز الإدراج في أرشيف الإنترنت (تمت أرشفته في 8 مارس 2015) - عرض توضيحي رسومي
• آدموفسكي، جون بول، فرز الإدراج الثنائي - لوحة النتائج - تحقيق كامل وتنفيذ بلغة C ، باثكوم، مؤرشف من الأصل في 24-02-2012 ، تم استرجاعه في 21-10-2009.
• فرز الإدراج – مقارنة مع خوارزميات الفرز الأخرى ذات التعقيد الزمني O(n²) ^، المملكة المتحدة : كور وور.
• فرز الإدراج (C) (ويكي)، LiteratePrograms– تطبيقات لخوارزمية فرز الإدراج في لغة C والعديد من لغات البرمجة الأخرى