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

خوارزمية الفرز أو الترتيب الفقاعي Bubble Sort Algorithm

اذهب الى الأسفل

خوارزمية الفرز أو الترتيب الفقاعي Bubble Sort Algorithm Empty خوارزمية الفرز أو الترتيب الفقاعي Bubble Sort Algorithm

مُساهمة من طرف زهراء الجمعة مارس 25, 2022 8:15 am

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

في هذا المقال سنناقش خوارزمية الفرز أو الترتيب الفقاعي #Bubble_Sort التي سُمّيت كذلك، ببساطة، لأن مع كل تكرار كامل ، ينتقل أكبر عنصر في مصفوفة معينة إلى آخر مكان في المصفوفة أو أعلى مؤشر ، تمامًا مثل ارتفاع فقاعة الماء على سطح الماء.

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



خوارزمية الترتيب الفقاعي هي خوارزميةٌ مبنيةٌ على فكرة المقارنة المتكررة بين زوجٍ من العناصر المتجاورة، وتبديل مواقعهم إذا كانوا في ترتيبٍ خاطئ.

ما هي آلية عمل الخوارزمية؟


نأخذ الخوارزمية مصفوفة من الأرقام غير المرتبة ثم تبدء حلقة دوران لفعل الاتى :

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

الخطوة الثانية : تبدء عملية تكرار جديدة للخطوة الاولى ، وفي كل تكرار تقارن الخوارزمية مع العنصر الأخير الذي لم يتم ترتيبه ،حيي يتم وضع جميع العناصر الفوضوية في مواقعها الصحيحة.
خوارزمية الفرز أو الترتيب الفقاعي Bubble Sort Algorithm 514705509

مثال توضيحي :

فلنفترض أنّ لدينا مصفوفة A غير مرتبةٍ تحتوي على n عنصر، والمطلوب هو ترتيب العناصر تصاعديًا، فلنفرض أنّ المصفوفة تحتوي على العناصر الآتية: {7, 4, 5, 2}

1_: مقارنة الرقم 4 مع الرقم 7، وبما أنّ 4 < 7، سيتم تبديل موقعيهما فيما بينهما، ولأن باقي العناصر أصغر من الـ 7، ستكرر العملية حتى يصبح رقم 7 في آخر المصفوفة.

الآن أصبحت المصفوفة بالشكل الآتي : {4, 5, 2, 7}

2_: مقارنة الرقم 5 مع الرقم 4 ، وبما أنّ 4 < 5، ومرتبين ترتيبًا تصاعديًا لن يتم تبديل موقعيهما. ثم مقارنة الرقم 5 مع الرقم 2، طبعًا بما أنّ 2 < 5، سيتمّ تبديل موقعيهما فيما بينهما.

الآن أصبحت المصفوفة بالشكل الآتي: {4, 2, 5, 7}

3_: مقارنة الرقم 4 مع الرقم 2، بما أنّ 2 < 4، سيتمّ تبديل موقعيهما فيما بينهما. لتصبح المصفوفة مرتبةً تصاعديًا بالشكل التالي: {2,4,5,7}.

مفهوم Swap أو تبادل المُحتوى


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

توجد عدة طرق لعمل #Swap لكن الطريقة الأكثر شهرة تقوم فكرتها على استخدام وسيط مساعد يُساعدنا على تبديل محتوى المتغيرين, فنضع قيمة المتغير الأول في الوسيط ثم نضع قيمة المتغير الثاني في المتغير الأول ثم نضع قيمة الوسيط في المتغير الثاني, و بهذا نكون قد بادلنا بين قيمة المتغير الأول و الثاني. لنفرض أن x=5 و y=-1  ....مثال :

الكود:

t = x //t = 5
x = y //x = -1
y = t //y = 5
في النهاية تكون x=-1 و y=5 . و بالتالي تم تبديل قيمتي x و y

شفرة الخوازرمية بالجافا :
الكود:
class BubbleSort
{
    void bubbleSort(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                {
                    // swap arr[j+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
    }
 
    /* Prints the array */
    void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver method to test above
    public static void main(String args[])
    {
        BubbleSort ob = new BubbleSort();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

شفرة الخوازرمية C :


الكود:
#include <stdio.h>
 
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)    
 
       // Last i elements are already in place  
       for (j = 0; j < n-i-1; j++)
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
 
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

شفرة الخوازرمية ++C :
الكود:
#include <bits/stdc++.h>
using namespace std;
 
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n-1; i++)    
    
    // Last i elements are already in place
    for (j = 0; j < n-i-1; j++)
        if (arr[j] > arr[j+1])
            swap(&arr[j], &arr[j+1]);
}
 
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver code
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout<<"Sorted array: \n";
    printArray(arr, n);
    return 0;
}

شفرة الخوازرمية بايثون :

الكود:
def bubbleSort(arr):
    n = len(arr)
 
    # Traverse through all array elements
    for i in range(n):
 
        # Last i elements are already in place
        for j in range(0, n-i-1):
 
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
 
bubbleSort(arr)
 
print ("Sorted array is:")
for i in range(len(arr)):
    print ("%d" %arr[i],end=" ")

شفرة الخوارزمية Php


الكود:
<?php
// PHP program for implementation
// of Bubble Sort

function bubbleSort(&$arr)
{
 $n = sizeof($arr);

 // Traverse through all array elements
 for($i = 0; $i < $n; $i++)
 {
 // Last i elements are already in place
 for ($j = 0; $j < $n - $i - 1; $j++)
 {
 // traverse the array from 0 to n-i-1
 // Swap if the element found is greater
 // than the next element
 if ($arr[$j] > $arr[$j+1])
 {
 $t = $arr[$j];
 $arr[$j] = $arr[$j+1];
 $arr[$j+1] = $t;
 }
 }
 }
}

// Driver code to test above
$arr = array(64, 34, 25, 12, 22, 11, 90);

$len = sizeof($arr);
bubbleSort($arr);

echo "Sorted array : \n";

for ($i = 0; $i < $len; $i++)
 echo $arr[$i]." ";

// This code is contributed by ChitraNayal.
?>
زهراء
زهراء
........
........

تاريخ التسجيل : 18/02/2011
المساهمات : 438
النقاط : 769
التقيم : 67
الدولة : مصر
الجنس : انثى

الرجوع الى أعلى الصفحة اذهب الى الأسفل

الرجوع الى أعلى الصفحة

ََ

مواضيع ذات صلة


 
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى