Complexity Analysis
الدرس 5 من 11 في دورة الفرز الفقاعي (Bubble Sort) على Coddy.
تحليل التعقيد لخوارزمية الترتيب الفقاعي (bubble sort).
يعتمد التعقيد الزمني على عدد المقارنات وعمليات التبديل التي يتم إجراؤها.
يتعين علينا إجراء n من الدورات وفي كل دورة لدينا (n-1) من المقارنات. حيث n هو عدد العناصر في القائمة.
إجمالي المقارنات=(n-1)+(n-1)+(n-1)....n من المرات
=n*(n-1)
=n2-n
التعقيد الزمني لخوارزمية الترتيب الفقاعي هو O(n2).
إذا تحدثنا عن التعقيد المكاني، فلا يتم استخدام مساحة إضافية في الخوارزمية، حيث يتم إجراء الترتيب في المكان (in-place) ويتم تنظيم العناصر في القائمة الأصلية نفسها.
التعقيد المكاني لخوارزمية الترتيب الفقاعي هو O(1) (ثابت).
التحدي
سهلأنشئ دالة باسم count_swaps تستقبل مصفوفة وحجم المصفوفة. قم بتنفيذ خوارزمية الترتيب الفقاعي (bubble sort) على المصفوفة واحسب عدد المرات التي يتم فيها التبديل.
جرّب بنفسك
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// اكتب الكود هنا
return 0;
}
جميع دروس الفرز الفقاعي (Bubble Sort)
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm