أنواع تربيعية
الفرز - يعيد ترتيب عناصر المصفوفة (القائمة) بترتيب معين.
طريقة الفقاعة (فرز الفقاعة) ، أو الفرز حسب التبادلات البسيطة.
الكلاسيكية الخالدة من هذا النوع. مبدأ العمل بسيط: نحن نلتف حول المصفوفة من البداية إلى النهاية ، في نفس الوقت نتبادل العناصر المجاورة غير المصنفة. نتيجة التمرير الأول إلى المكان الأخير ، "تنبثق" أقصى عنصر. الآن نتجاوز مرة أخرى الجزء غير الفرز من المصفوفة (من العنصر الأول إلى العنصر قبل الأخير) ونغير الجيران غير الفرز على طول الطريق. ثاني أكبر عنصر سيكون في المكان قبل الأخير. بالاستمرار بنفس الروح ، سوف نتجاوز الجزء غير الفرز المتناقص باستمرار من المصفوفة ، ودفع الحدود القصوى التي تم العثور عليها إلى النهاية.
نبسب ؛
المصدر
تنفيذ حسابي لهذه الخوارزمية
<قبل>
الحلقات لـ J = 1 إلى N-1 الخطوة 1
F = 0
LOOP FOR I = 1 إلى N-J-1 الخطوة 1
إذا كان A [I] & GT. أ [I + 1] بعد ذلك
التبادل أ [أنا] ، أ [أنا + 1]
F = 1
بعدها انا
إذا كانت F = 0 ، فاخرج من الحلقة // إذا لم تكن هناك عمليات تبادل أثناء المرور ،
نبسب ؛ // هذا يعني كل العناصر
نبسب ؛ // مرتبة بالترتيب
التالي ياء
درجة تعقيد هذه الخوارزمية: & nbsp؛ \ (\ displaystyle O (n ^ {2}) \) .
معلومات إضافية مفيدة: & nbsp؛ مقالة Wikipedia .
نبسب ؛
|
إدراج فرز
فرز الإدراج & nbsp؛ ( ترتيب الإدراج ) & nbsp؛ & mdash؛ & nbsp ؛ خوارزمية الفرز التي يتم فيها البحث عن عناصر تسلسل الإدخال واحدًا تلو الآخر ، ويتم وضع كل عنصر وارد جديد في المكان المناسب بين العناصر التي تم فرزها مسبقًا.
 أدخل الترتيب & ndash؛ إنها خوارزمية بسيطة للغاية ولكنها غير فعالة ومع ذلك لها العديد من المزايا المحددة التي تجعلها ذات صلة حتى بعد تطوير العديد من الخوارزميات الأخرى الأكثر كفاءة بشكل عام.
من خلال فرز الإدراج ، لا يلزم أن تكون المصفوفة بأكملها في المقدمة قبل الفرز. يمكن أن تتلقى الخوارزمية عنصرًا واحدًا في كل مرة أثناء الفرز. هذا مفيد جدًا إذا احتجنا إلى إضافة المزيد من العناصر أثناء الفرز. ستقوم الخوارزمية بإدراج العنصر الجديد في المكان الصحيح بدون "إعادة التنفيذ" فرز المصفوفة بأكملها .
يمكن استخدام فرز الإدراج في الممارسة العملية نظرًا لكفاءته على مجموعات البيانات الصغيرة (~ 10 عناصر).
تكمن المشكلة في هذا: يوجد جزء من المصفوفة تم فرزه بالفعل ، وتريد إدراج العناصر المتبقية من المصفوفة في الجزء المصنف ، مع الحفاظ على الترتيب. للقيام بذلك ، في كل خطوة من الخوارزمية ، نختار أحد عناصر بيانات الإدخال ونقوم بإدخاله في الموضع المطلوب في الجزء الذي تم فرزه بالفعل من المصفوفة ، حتى يتم فرز مجموعة بيانات الإدخال بالكامل. طريقة اختيار العنصر التالي من مصفوفة الإدخال تعسفية ، ولكن عادةً (ومن أجل الحصول على خوارزمية فرز مستقرة) ، يتم إدراج العناصر بترتيب ظهورها في مصفوفة الإدخال.
تنفيذ حسابي لهذه الخوارزمية
<قبل>
// يعتبر العنصر الفارغ تسلسلاً تم فرزه بالفعل.
// لذلك تبدأ الحلقة من 1
الحلقات الخاصة بـ I = 1 إلى N-1 الخطوة 1
X = A [I]
J = أنا
عندما J & gt؛ 0 AND A [J-1] & gt؛ X // يبحثان عن مكان لإدراجه
تبادل أ [J] ، أ [J-1]
J = J-1
في النهاية وداعا
أ [J] = X
بعدها انا
التعقيد الحسابي: & nbsp؛ \ (\ displaystyle O (n ^ {2}) \) .
|