مقدمة في خوارزمية فرز الفقاعات

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

في هذه المقالة ، ستتعرف على عمل خوارزمية فرز الفقاعات ، الرمز الزائف لفرز الفقاعات الخوارزمية ، وتعقيدها في الوقت والمكان ، وتنفيذها في لغات البرمجة المختلفة مثل C ++ و Python و C و جافا سكريبت.

كيف تعمل خوارزمية فرز الفقاعات؟

الفرز الفقاعي هو أبسط خوارزمية فرز تتخطى القائمة بشكل متكرر ، وتقارن العناصر المجاورة ، وتبديلها إذا كانت بالترتيب الخاطئ. يمكن شرح هذا المفهوم بشكل أكثر كفاءة بمساعدة مثال. ضع في اعتبارك مصفوفة لم يتم فرزها تحتوي على العناصر التالية: {16 ، 12 ، 15 ، 13 ، 19}.

مثال:

تتم هنا مقارنة العناصر المجاورة وإذا لم تكن بترتيب تصاعدي ، يتم تبديلها.

الكود الزائف لخوارزمية فرز الفقاعات

في الكود الكاذب، يمكن التعبير عن خوارزمية Bubble Sort على النحو التالي:

BubbleSort (Arr [] ، الحجم)
// حلقة للوصول إلى كل عنصر من عناصر المصفوفة





instagram viewer


بالنسبة إلى i = 0 إلى الحجم -1 افعل:
// حلقة لمقارنة عناصر المصفوفة
بالنسبة إلى j = 0 للحجم i-1 افعل:
// قارن العناصر المجاورة
إذا Arr [j]> Arr [j + 1] ثم
// بدلها
مبادلة (Arr [j]، Arr [j + 1])
إنهاء إذا
نهاية ل
نهاية ل
نهاية

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

وبالتالي ، يمكن التعبير عن الشفرة الزائفة لخوارزمية فرز الفقاعات المحسّنة على النحو التالي:

BubbleSort (Arr [] ، الحجم)
// حلقة للوصول إلى كل عنصر من عناصر المصفوفة
بالنسبة إلى i = 0 إلى الحجم -1 افعل:
// تحقق من حدوث المبادلة
مبادلة = خطأ
// حلقة لمقارنة عناصر المصفوفة
بالنسبة إلى j = 0 للحجم i-1 افعل:
// قارن العناصر المجاورة
إذا Arr [j]> Arr [j + 1] ثم
// بدلها
مبادلة (Arr [j]، Arr [j + 1])
مبادلة = صحيح
إنهاء إذا
نهاية ل
// إذا لم يتم تبديل أي عناصر ، فهذا يعني أن المصفوفة مرتبة الآن ، ثم كسر الحلقة.
إذا (لم يتم تبديلها) إذن
فترة راحة
إنهاء إذا
نهاية ل
نهاية

تعقيد الوقت والمساحة الإضافية لخوارزمية فرز الفقاعات

التعقيد الزمني الأسوأ لخوارزمية فرز الفقاعات هو O (n ^ 2). يحدث ذلك عندما تكون المصفوفة بترتيب تنازلي وتريد فرزها بترتيب تصاعدي أو العكس.

أفضل تعقيد زمني لخوارزمية فرز الفقاعات هو O (n). يحدث عندما يتم فرز المصفوفة بالفعل.

متعلق ب: ما هو تدوين Big-O؟

متوسط ​​تعقيد وقت الحالة لخوارزمية فرز الفقاعات هو O (n ^ 2). يحدث عندما تكون عناصر المصفوفة في ترتيب مختلط.

المساحة الإضافية المطلوبة لخوارزمية فرز الفقاعات هي O (1).

C ++ تنفيذ خوارزمية فرز الفقاعات

فيما يلي تطبيق C ++ لخوارزمية Bubble Sort:

// C ++ تنفيذ
// خوارزمية فرز الفقاعات المحسّنة
#تضمن 
استخدام اسم للمحطة؛
// وظيفة لأداء Bubble Sort
تصنيف فقاعي فارغ (int arr [] ، حجم int) {
// حلقة للوصول إلى كل عنصر من عناصر المصفوفة
لـ (int i = 0 ؛ أنا // متغير للتحقق من حدوث المبادلة
منطقية مبادلة = خطأ ؛
// حلقة لمقارنة عنصرين متجاورين من المصفوفة
لـ (int j = 0 ؛ j // مقارنة عنصري مصفوفة متجاورتين
إذا (arr [j]> arr [j + 1]) {
// قم بتبديل كلا العنصرين إذا كانا كذلك
// ليس بالترتيب الصحيح
int temp = arr [j] ؛
arr [j] = arr [j + 1] ؛
arr [j + 1] = temp ؛
مبادلة = صحيح ؛
}
}
// إذا لم يتم تبديل أي عناصر ، فهذا يعني أن المصفوفة مرتبة الآن ،
// ثم كسر الحلقة.
إذا (مبادلة == خطأ) {
فترة راحة؛
}
}
}
// يطبع عناصر المصفوفة
باطل printArray (int arr []، int size) {
لـ (int i = 0 ؛ أنا cout << arr [i] << ""؛
}
cout << endl؛
}
انت مين() {
int arr [] = {16، 12، 15، 13، 19} ؛
// إيجاد طول المصفوفة
حجم int = sizeof (arr) / sizeof (arr [0]) ؛
// طباعة المصفوفة التي لم يتم فرزها
cout << "Unsorted Array:" << endl؛
printArray (حجم ، حجم) ؛
// استدعاء الدالة bubbleSort ()
BubbleSort (حجم آر ، حجم) ؛
// طباعة المصفوفة المرتبة
cout << "مصفوفة مرتبة بترتيب تصاعدي:" << endl؛
printArray (حجم ، حجم) ؛
العودة 0 ؛
}

انتاج:

صفيف غير مفرز: 
16 12 15 13 19 
مصفوفة مرتبة بترتيب تصاعدي:
12 13 15 16 19

تنفيذ Python لخوارزمية فرز الفقاعات

يوجد أدناه تطبيق Python لخوارزمية Bubble Sort:

# تنفيذ Python لملف
# خوارزمية فرز الفقاعات المحسنة
# وظيفة لأداء Bubble Sort
def BubbleSort (حجم ، حجم):
# حلقة للوصول إلى كل عنصر من عناصر القائمة
لأني في النطاق (الحجم -1):
# متغير للتحقق من حدوث المبادلة
مبادلة = خطأ
# حلقة لمقارنة عنصرين متجاورين في القائمة
لـ j في النطاق (الحجم- i-1):
# مقارنة عنصرين متجاورين في القائمة
إذا arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
مبادلة = صحيح
# إذا لم يتم تبديل أي عناصر ، فهذا يعني أن القائمة مرتبة الآن ،
# ثم كسر الحلقة.
إذا تم التبديل == خطأ:
فترة راحة
# يطبع عناصر القائمة
def printArray (arr):
للعنصر في آر:
طباعة (عنصر ، نهاية = "")
مطبعة("")
arr = [16 ، 12 ، 15 ، 13 ، 19]
# إيجاد طول القائمة
الحجم = len (arr)
# طباعة القائمة المعطاة التي لم يتم فرزها
طباعة ("قائمة غير مرتبة:")
printArray (arr)
# استدعاء الدالة BubbleSort ()
BubbleSort (حجم متوسط)
# طباعة القائمة التي تم فرزها
طباعة ("القائمة المصنفة بترتيب تصاعدي:")
printArray (arr)

انتاج:

قائمة غير مرتبة:
16 12 15 13 19 
قائمة مرتبة بترتيب تصاعدي:
12 13 15 16 19

متعلق ب: كيفية استخدام For Loops في Python

ج ـ تنفيذ خوارزمية الفرز الفقاعي

فيما يلي تنفيذ C لخوارزمية Bubble Sort:

// ج تنفيذ
// خوارزمية فرز الفقاعات المحسّنة
#تضمن 
#تضمن 
// وظيفة لأداء Bubble Sort
تصنيف فقاعي فارغ (int arr [] ، حجم int) {
// حلقة للوصول إلى كل عنصر من عناصر المصفوفة
لـ (int i = 0 ؛ أنا // متغير للتحقق من حدوث المبادلة
منطقية مبادلة = خطأ ؛
// حلقة لمقارنة عنصرين متجاورين من المصفوفة
لـ (int j = 0 ؛ j // مقارنة عنصري مصفوفة متجاورتين
إذا (arr [j]> arr [j + 1]) {
// قم بتبديل كلا العنصرين إذا كانا كذلك
// ليس بالترتيب الصحيح
int temp = arr [j] ؛
arr [j] = arr [j + 1] ؛
arr [j + 1] = temp ؛
مبادلة = صحيح ؛
}
}
// إذا لم يتم تبديل أي عناصر ، فهذا يعني أن المصفوفة مرتبة الآن ،
// ثم كسر الحلقة.
إذا (مبادلة == خطأ) {
فترة راحة؛
}
}
}
// يطبع عناصر المصفوفة
باطل printArray (int arr []، int size) {
لـ (int i = 0 ؛ أنا printf ("٪ d"، arr [i]) ؛
}
printf ("\ ⁠n") ؛
}
انت مين() {
int arr [] = {16، 12، 15، 13، 19} ؛
// إيجاد طول المصفوفة
حجم int = sizeof (arr) / sizeof (arr [0]) ؛
// طباعة المصفوفة التي لم يتم فرزها
printf ("صفيف غير مصنف: \ ⁠n") ؛
printArray (حجم ، حجم) ؛
// استدعاء الدالة bubbleSort ()
BubbleSort (حجم آر ، حجم) ؛
// طباعة المصفوفة المرتبة
printf ("مصفوفة مرتبة بترتيب تصاعدي: \ ⁠n") ؛
printArray (حجم ، حجم) ؛
العودة 0 ؛
}

انتاج:

صفيف غير مفرز: 
16 12 15 13 19 
مصفوفة مرتبة بترتيب تصاعدي: 
12 13 15 16 19

تنفيذ JavaScript لخوارزمية فرز الفقاعات

فيما يلي تطبيق JavaScript لخوارزمية Bubble Sort:

// تنفيذ JavaScript لملف
// خوارزمية فرز الفقاعات المحسّنة
// وظيفة لأداء Bubble Sort
وظيفة BubbleSort (حجم ، حجم) {
// حلقة للوصول إلى كل عنصر من عناصر المصفوفة
لـ (دع أنا = 0 ؛ أنا// متغير للتحقق من حدوث المبادلة
فار مبادلة = خطأ ؛
// حلقة لمقارنة عنصرين متجاورين من المصفوفة
لـ (دع j = 0 ؛ ي// مقارنة عنصري مصفوفة متجاورتين
إذا (arr [j]> arr [j + 1]) {
// قم بتبديل كلا العنصرين إذا كانا كذلك
// ليس بالترتيب الصحيح
اسمحوا temp = arr [j] ؛
arr [j] = arr [j + 1] ؛
arr [j + 1] = temp ؛
مبادلة = صحيح ؛
}
// إذا لم يتم تبديل أي عناصر ، فهذا يعني أن المصفوفة مرتبة الآن ،
// ثم كسر الحلقة.
إذا (مبادلة == خطأ) {
فترة راحة؛
}
}
}
}
// يطبع عناصر المصفوفة
وظيفة printArray (حجم ، حجم) {
لـ (دع أنا = 0 ؛ أناdocument.write (arr [i] + "") ؛
}
document.write ("
")
}
var arr = [16، 12، 15، 13، 19] ؛
// إيجاد طول المصفوفة
حجم فار = الطول الطول ؛
// طباعة المصفوفة التي لم يتم فرزها
document.write ("صفيف غير مصنف: 
");
printArray (حجم ، حجم) ؛
// استدعاء الدالة bubbleSort ()
BubbleSort (حجم آر ، حجم) ؛
// طباعة المصفوفة المرتبة
document.write ("مصفوفة مرتبة بترتيب تصاعدي: 
");
printArray (حجم ، حجم) ؛

انتاج:

صفيف غير مفرز:
16 12 15 13 19
مصفوفة مرتبة بترتيب تصاعدي:
12 15 13 16 19

أنت الآن تفهم عمل خوارزمية فرز الفقاعات

الفرز الفقاعي هو أبسط خوارزمية الفرز ويستخدم بشكل أساسي لفهم أسس الفرز. يمكن أيضًا تنفيذ Bubble Sort بشكل متكرر ، لكنه لا يوفر أي مزايا إضافية للقيام بذلك.

باستخدام Python ، يمكنك تنفيذ خوارزمية Bubble Sort بسهولة. إذا لم تكن معتادًا على Python وترغب في بدء رحلتك ، فإن البدء بنص "Hello World" يعد خيارًا رائعًا.

كيف تبدأ مع Python باستخدام البرنامج النصي "Hello World"

Python هي واحدة من أشهر لغات البرمجة المستخدمة اليوم. اتبع هذا البرنامج التعليمي لتبدأ باستخدام أول برنامج نصي من Python.

اقرأ التالي

عن المؤلف