الفرز الداخلي باستخدام التضمين المباشر. الفرز باستخدام التضمين المباشر

الفرز حسب التضمين المباشر هو نفس الفرز حسب اختيار بسيط، يُستخدم عادةً للمصفوفات التي لا تحتوي على عناصر مكررة.

يتم الفرز بهذه الطريقة بالتتابع خطوة بخطوة. على ك-الخطوة الرابعة هي أن الجزء من المصفوفة يحتوي على الجزء الأول ك-تم طلب عنصر واحد بالفعل، وهو .

التالي عليك أن تأخذ كالعنصر واختيار مكان له في الجزء الذي تم فرزه من المصفوفة بحيث لا يتم تعطيل الترتيب بعد إدراجه، أي أنك تحتاج إلى العثور على هذا العنصر. ثم تحتاج إلى إدراج العنصر أ(ك)إلى المكان الذي تم العثور عليه.

مع كل خطوة، يزداد الجزء الذي تم فرزه من المصفوفة. لإجراء فرز كامل سوف تحتاج إلى تشغيل ن-خطوة واحدة.

يبقى الإجابة على سؤال حول كيفية العثور على المكان المناسب للعنصر X. دعونا نتصرف على النحو التالي: سننظر إلى العناصر الموجودة على اليسار X(أي تلك التي تم طلبها بالفعل)، متجهة نحو بداية المصفوفة. بحاجة لعرض العناصر أ(ي), ييختلف من ك-من l إلى 1. وتنتهي هذه المشاهدة عند استيفاء أحد الشروط التالية:

تم العثور على عنصر يشير إلى الحاجة إلى الإدراج Xبين و أ(ي).

تم الوصول إلى الطرف الأيسر من الجزء المطلوب من المصفوفة، لذلك نحن بحاجة إلى الإدراج Xإلى المركز الأول.

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

يتم توضيح تقنية الفرز في الجدول 2:

الجدول 2 - مثال على الفرز باستخدام التضمين المباشر

يتكون التسلسل المرتب في البداية من العنصر الأول 9. العنصر أ( 2) =5 - الأول من التسلسل غير المرتب و5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент أ( 3) =15 من المتوالية غير المرتبة أكبر من جميع عناصر المتتابعة المرتبة، وبالتالي تبقى في مكانها وفي الخطوة التالية تتكون المتتابعة المرتبة من 5، 9، 15، والعنصر المعني هو 6. وتستمر العملية حتى يصبح التسلسل مرتبًا.

فرز شاكر

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

تعتمد طريقة شاكر الفرز على هذه الملاحظات. عند استخدامه، يتغير اتجاه العرض التسلسلي في كل خطوة تالية. ونتيجة لذلك، في خطوة واحدة "يطفو" العنصر الأخف التالي، وفي الخطوة التالية "يغرق" العنصر الأثقل التالي. ويرد مثال على فرز شاكر في الجدول 3.

الجدول 3 - مثال على فرز شاكر

فرز مصفوفة باستخدام التضمينات ذات المسافات المتناقصة (طريقة Shell)

اقترح د. شيل تحسينًا في الفرز باستخدام التضمين المباشر.

فكرة الطريقة : يتم تقسيم جميع عناصر المصفوفة إلى مجموعات بحيث تضم كل مجموعة عناصر متباعدة عن بعضها البعض بعدد معين من المواضع ل. يتم فرز عناصر كل مجموعة. بعد ذلك، يتم دمج جميع العناصر مرة أخرى وفرزها في مجموعات، بينما تقل المسافة بين العناصر. تنتهي العملية بعد ترتيب العناصر بمسافة بينها تساوي 1.

ويرد في الجدول 4 مثال للفرز باستخدام طريقة Shell.

الجدول 4 - مثال على الفرز باستخدام طريقة Shell

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

الفرز المقسم (الفرز السريع)

تم اقتراح طريقة الفرز المقسم بواسطة تشارلز هور. تعتبر هذه الطريقة تطويرًا لطريقة التبادل البسيطة وهي فعالة جدًا لدرجة أنها أصبحت تسمى طريقة الفرز السريع.

الفكرة الرئيسية للخوارزمية هي ذلك بشكل عشوائيتم تحديد بعض عناصر المصفوفة س، وبعد ذلك يتم اجتياز المصفوفة من اليسار حتى يتم العثور على عنصر ما أ (ط)مثل ذلك أ (ط) > سومن ثم يتم اجتياز المصفوفة من اليمين حتى تتم مواجهة العنصر أ (ط)مثل ذلك أ (ط)< س. ويتم تبديل هذين العنصرين، وتستمر عملية التصفح والمقارنة والتبادل حتى نصل إلى العنصر س. ونتيجة لذلك، سيتم تقسيم المصفوفة إلى جزأين - الجزء الأيسر، حيث ستكون القيم الأساسية أصغر س، والصحيح مع القيم الرئيسية أكبر س. تستمر العملية بعد ذلك بشكل متكرر للجانبين الأيمن والأيسر من المصفوفة حتى يحتوي كل جزء على عنصر واحد بالضبط. يمكن استبدال العودية بالتكرارات إذا كنت تتذكر مؤشرات المصفوفة المقابلة.

يتم عرض عملية فرز مصفوفة باستخدام الطريقة السريعة في الجدول 5.

الجدول 5 - مثال على الفرز السريع

الفرز هو ترتيب البيانات في الذاكرة بطريقة منتظمة وفقًا للمعلمة المحددة. يعتبر الانتظام بمثابة زيادة (نقصان) في قيمة المعلمة من بداية مصفوفة البيانات إلى نهايتها.

عند معالجة البيانات، من المهم معرفة مجال المعلومات الخاص بالبيانات وموقعها في الجهاز.

هناك فرز داخلي وخارجي:

الفرز الداخلي - الفرز ذاكرة الوصول العشوائي;

الفرز الخارجي - الفرز في الذاكرة الخارجية.

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

عند الفرز، قد تظهر مفاتيح متطابقة. في هذه الحالة، من المستحسن، بعد الفرز، ترتيب المفاتيح المتطابقة بنفس الترتيب كما في مصدر الملف. هذا - فرز مستقر.

سننظر فقط في الأنواع التي لا تستخدم ذاكرة الوصول العشوائي الإضافية. تسمى مثل هذه الأنواع "في نفس المكان".

يمكن اعتبار فعالية الفرز وفقًا لعدة معايير:

الوقت المستغرق في الفرز؛

مقدار ذاكرة الوصول العشوائي (RAM) المطلوبة للفرز؛

الوقت الذي يقضيه المبرمج في كتابة البرنامج.

دعونا نسلط الضوء على المعيار الأول. ويمكن اعتبار ما يعادل الوقت المستغرق في الفرز عدد المقارناتو عدد الحركاتعند إجراء الفرز.

ترتيب عدد المقارنات والحركات أثناء الفرز يكمن في الداخل

من O (n log n) إلى O (n 2);

O(n) هي حالة مثالية وبعيدة المنال.

تتميز طرق الفرز التالية:

الأساليب الصارمة (المباشرة)؛

أساليب محسنة.

أساليب صارمة:

طريقة الإدراج المباشر؛

طريقة الاختيار المباشر

طريقة التبادل المباشر.

فعالية الأساليب الصارمة هي نفسها تقريبًا.

الفرز المباشر

تنقسم العناصر ذهنياً إلى تسلسل جاهز a 1 ,...,a i-1 والتسلسل الأصلي.

في كل خطوة، بدءًا من i = 2 وزيادة i في كل مرة بمقدار واحد، نستخرج من التسلسل الأصلي العنصر الأولويتم نقله إلى التسلسل النهائي، بينما يتم إدخاله في المكان الصحيح.

جوهر الخوارزمية هو هذا:

لأني = 2 إلى ن

س = أ(ط)

نجد مكانًا بين a(1)…a(i) لإدراج x

بعدها انا

هناك نوعان من خوارزميات الفرز الأمامي. فالأولى بلا حاجز

خوارزمية فرز التضمين المباشر بدون عائق

لأني = 2 إلى ن

س = أ(ط)

بالنسبة لـ j = i - 1 وصولاً إلى 1

إذا س< a(j)

ثم أ(ي + 1) = أ(ي)

وإلا اذهب إلى L

إنهاء إذا

التالي ي

ل: أ(ي + 1) = س

بعدها انا

يعود

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

خوارزمية فرز التضمين المباشر مع الحاجز

لأني = 2 إلى ن

س = أ(ط)

أ(0) = س (أ(0) - الحاجز)

ي = ط - 1

بينما س< a(j) do

أ(ي +1) = أ(ي)

ي = ي - 1

في نهاية المطاف

أ(ي +1) = س

بعدها انا

يعود

كفاءة خوارزمية التغذية الأمامية

عدد المقارنات الرئيسية Ci أثناء الغربلة i هو على الأكثر i-1، على الأقل 1؛ إذا افترضنا أن جميع التباديل لمفاتيح N متساوية في الاحتمال، فإن متوسط ​​عدد المقارنات = i/2. عدد التحويلات Mi=Ci+3 (بما في ذلك الحاجز). تحدث الحد الأدنى من التقديرات في حالة وجود تسلسل أولي مرتب بالفعل للعناصر، في حين تحدث أسوأ التقديرات عندما يتم ترتيبها مبدئيًا بترتيب عكسي. في بعض النواحي، يُظهر الفرز المتضمن سلوكًا طبيعيًا حقًا. من الواضح أن الخوارزمية المذكورة أعلاه تصف عملية الفرز المستقر: يبقى ترتيب العناصر ذات المفاتيح المتساوية دون تغيير.

عدد المقارنات في أسوأ الحالات، عندما يتم فرز المصفوفة بالطريقة المعاكسة، C max = n(n - 1)/2، أي - O (n 2). عدد التباديل M max = C max + 3(n-1)، أي. - على 2). إذا تم فرز المصفوفة بالفعل، فسيكون عدد المقارنات والتباديل ضئيلًا: C min = n-1; م دقيقة = =3(ن-1).

الفرز باستخدام التبادل المباشر (فرز الفقاعة)

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

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

C دقيقة = ن - 1، ترتيب O(ن)،

ولا توجد حركة على الإطلاق

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

تُعرف هذه الطريقة عادةً باسم فرز الفقاعات.

خوارزمية طريقة التبادل المباشر

لـ j = n إلى i الخطوة -1

إذا (ي)< a(j - 1) then

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

فلوريدا = صحيح

إذا فلوريدا = كاذبة ثم العودة

فلوريدا = خطأ

لـ j = n إلى i الخطوة -1

إذا (ي)< a(j - 1) then

فلوريدا = صحيح

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

كفاءة خوارزمية فرز التبادل المباشر

عدد المقارنات C max = n(n-1)/2، ترتيب O(n 2).

عدد الحركات M max = 3C max = 3n(n-1)/2، ترتيب O(n 2).

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

التعريفات اللازمة وتصنيف الفرز.

فرز. التعريفات اللازمة وتصنيف الفرز. التضمين المباشر وفرز الاختيار. فعاليتها

فرز– هذا هو ترتيب البيانات في الذاكرة بشكل منتظم حسب مفاتيحها. لذلك، عند معالجة البيانات، من المهم معرفة مجال المعلومات الخاص بالبيانات وموضعها في الجهاز. ولذلك يميزون داخلي(الفرز في ذاكرة الوصول العشوائي) و الفرز الخارجي(الفرز في الذاكرة الخارجية). الانتظامترتيب العناصر هو الزيادة (النقصان) في قيمة المفتاح من البداية إلى النهاية في المصفوفة.

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

يمكن اعتبار كفاءة الفرز من خلال عدة معايير:

1) الوقت المستغرق في الفرز؛

2) مقدار ذاكرة الوصول العشوائي (RAM) المطلوبة للفرز؛

3) الوقت الذي يقضيه المبرمج في كتابة البرنامج.

يتناسب الوقت المستغرق في الفرز مع عدد المقارنات التي يتم إجراؤها أثناء الفرز وعدد مرات نقل العناصر.

ويعتقد أن ترتيب رقم المقارنة عند الفرز يمكن أن يتراوح من س (تسجيل الدخول)قبل على 2)، أين على)- حالة مثالية وبعيدة المنال.

يمكن تصنيف طرق الفرز تقريبًا على النحو التالي:

1) الأساليب الصارمة (المباشرة).(فعاليتها هي نفسها تقريبًا):

· اتصال مباشر;

· الاختيار المباشر;

· التبادل المباشر;

2) تحسين الأساليب.

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

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

لنأخذ مثالاً للفرز باستخدام طريقة التضمين المباشر على سلسلة من العناصر: 10، 3، 11، 8، 2، 15، 44، 9 (الجدول 11.1). يجب فرزها بترتيب تصاعدي.

في البداية، لا يحتوي التسلسل النهائي على أي عناصر. في الخطوة الأولى، يصبح العنصر الأول في التسلسل الأصلي، 10، هو العنصر الأول في التسلسل النهائي. التالي هو الخطوة الثانية: يتم وضع العنصر 3 من التسلسل الأصلي في العنصر النهائي. تسير الأمور على هذا النحو. إذا كان العنصر أكبر من 10 فإنه يبقى في مكانه، وإذا كان أقل من ذلك، يتم إزاحة 10 وحدة واحدة إلى اليمين ويوضع العنصر في مكانه. منذ 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10، ثم يبقى 11 في مكانه. التسلسل الأصلي الآن هو: 8، 2، 15، 44، 9. ويتم تنفيذ الخطوات اللاحقة بنفس الطريقة.

الجدول 11.1

مبدأ التشغيل لفرز التضمين المباشر

وعدد خطوات هذا الفرز (الجدول 11.1) يساوي عدد العناصر في التسلسل المفرز، أي: 8 خطوات = 8 عناصر.

هناك طريقتان للتنفيذ هذه الطريقة- هذا بدون حاجز (الشكل 11.1) وبحاجز (الشكل 11.2).

يمكن تحسين طريقة الإدراج المباشر من خلال إيجاد مكان السجل المدرج في الجدول الفرعي المرتب باستخدام هذه الطريقة الثنائية (ثنائي، ثنائي، لوغاريتمي)يبحث. يسمى هذا التعديل لطريقة الإدراج إدراج مع إدراج ثنائي.

دعونا نفكر ي– خطوة الفرز ( ي=2, 3, ..., ن). لو ك[ ي]>= ك[ ي-1] إذن لم يتم انتهاك النظام وعلينا أن ننتقل إلى ذلك ر[ ي+1]– يا السجلات. لو ك[ ي]< ك[ ي-1] ، الذي - التي ر[ ي] المخزنة في متغير العمل (راب= ر[ ي]) ويتم البحث عن مكان له في الجزء المرتب من الجدول - في الجدول الفرعي. دعونا نشير إلى الحد الأدنى لمؤشر هذا الجدول الفرعي بـ نانوغرام، من أعلى إلى أسفل vg (في الأصل نانوغرام=1. vg=ي-1).

وفقا للبحث الثنائي المفتاح ك[ ي] السجل المعني ر[ ي] يجب أولا مقارنة مع المفتاح ك[ أنا] السجلات ر[ أنا] ، الموجود في منتصف الجدول الفرعي المطلوب (i=(ng+vg) شعبة 2). لو ك[ ي]> ك[ أنا], ثم يتم تجاهل الجانب الأيسر من الجدول الفرعي - السجلات ذات المفاتيح الأصغر - (أي لم تعد تؤخذ في الاعتبار) (نانوغرام= أنا+1) . لو ك[ ي]< ك[ أنا] ، ثم يتم تجاهل الجانب الأيمن من الجدول الفرعي - السجلات ذات المفاتيح الكبيرة (vg= أنا-1). يستمر البحث في بقية الجدول الفرعي. تستمر عملية تقسيم أجزاء الجدول الفرعي إلى نصفين حتى حدوث أحد الحالات التالية:

1) ك[ ي]= ك[ أنا] ، لذلك، (ط+1)الموضع -th هو موقع الإدخال المعني. دعونا ننقل السجلات ر[ أنا+1], ر[ أنا+2], …, ر[ ي-1] موضع واحد إلى اليمين وبالتالي توفير مساحة للإدراج (ر[ أنا+1]= راب).

2) ك[ ي]<> ك[ أنا] و نانوغرام> vg - المفاتيح غير متطابقة، وطول الجدول الفرعي الأخير هو 1. في هذه الحالة، يكون موقع الإدراج هو الموضع نانوغرام, هكذا يسجل ر[ نانوغرام], ر[ نانوغرام+1], … , ر[ ي-1] يجب أن يتم نقل موضع واحد إلى اليمين (ر[ نانوغرام]= راب) .

تم وصف خوارزمية البحث الثنائي بالتفصيل في قسم "البحث عن المطابقة الثنائية".

لنلقي نظرة على مثال ي- خطوة الفرز (يتم تحديد موقع السجل بالمفتاح الذي يساوي 9؛ ي=7, ك[ ي]=9 ):

متوسط ​​عدد المقارنات لهذه الطريقة هو nlog 2 (ن).

طريقة الإدراج ذات المسارين

طريقة الإدراج ذات المسارينهو تعديل لطريقة الإدراج المباشر؛ أنه يحسن أداء الفرز.

لتنفيذ هذه الطريقة، يلزم مقدار إضافي من الذاكرة يساوي المقدار الذي يشغله الجدول المراد فرزه (دعنا نسميها منطقة الإخراج ت). في الخطوة الأولى من الفرز إلى منتصف منطقة الإخراج (الموضع م=(ن شعبة 2)+1) يتم وضع سجل الجدول الأول ر.مواقف أخرى تفارغة في الوقت الراهن. في خطوات الفرز اللاحقة، مفتاح السجل التالي ر[ ي] (ي=2, 3, …, ن) تتم مقارنتها بمفتاح الإدخال ت[ م] واعتمادًا على نتائج المقارنة، هناك مساحة لـ ر[ ي] عثر عليه في تإلى اليسار أو اليمين ت[ م] عن طريق طريقة الإدراج. في هذه الحالة، أرقام أقصى اليسار ( ل) وأقصى اليمين ( ص) العناصر المدرجة في منطقة الإخراج. القيم النهائية لو صمتساوي 1 و نعلى التوالى.

يجب أن تأخذ الخوارزمية أيضًا في الاعتبار المواقف التالية:

مفتاح الكتابة ص[ي]أقل من مفتاح الكتابة تي [م]، لكن ل = 1;

مفتاح الكتابة ص[ي]المزيد من مفتاح الكتابة تي [م]، لكن ص = ن.

في هذه الحالات، لإدراج سجل ر[ ي] من الضروري نقل سجلات الجدول الفرعي مع السجل ت[ م] اليمين أو اليسار (يستخدم طريقة الإدراج المباشر).

دعونا نلقي نظرة على مثال للفرز باستخدام هذه الطريقة.

دع التسلسل الأولي لمفاتيح الجدول يبدو كما يلي:

24, 1, 28, 7, 25, 3, 6, 18, 8 (ن=9, م=(ن شعبة 2)+ 1=5)

رقم الخطوة	منطقة الإخراج