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

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

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

---

---

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

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

مثال:

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

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

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

bubbleSort(Arr[], size)
// loop to access each array element
for i=0 to size-1 do:
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
end if
end for
end for
end


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

---

---

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

bubbleSort(Arr[], size)
// loop to access each array element
for i=0 to size-1 do:
// check if swapping occurs
swapped = false
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
swapped = true
end if
end for
// if no elements were swapped that means the array is sorted now, then break the loop.
if(not swapped) then
break
end if
end for
end


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

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

---

---

كيفية زيادة ذاكرة الوصول العشوائي على الكمبيوتر

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

كيف يمكنني معرفة ما إذا تم حظري على facebook

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

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

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

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

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

// C++ implementation of the
// optimised Bubble Sort algorithm
#include
using namespace std;
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j <(size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i cout << arr[i] << ' ';
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
cout << 'Unsorted Array: ' << endl;
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
cout << 'Sorted Array in Ascending Order:' << endl;
printArray(arr, size);
return 0;
}


انتاج:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19

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

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

# Python implementation of the
# optimised Bubble Sort algorithm

# Function to perform Bubble Sort
def bubbleSort(arr, size):
# Loop to access each element of the list
for i in range (size-1):
# Variable to check if swapping occurs
swapped = False
# loop to compare two adjacent elements of the list
for j in range(size-i-1):
# Comparing two adjacent list elements
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = True
# If no elements were swapped that means the list is sorted now,
# then break the loop.
if swapped == False:
break
# Prints the elements of the list
def printArray(arr):
for element in arr:
print(element, end=' ')
print('')

arr = [16, 12, 15, 13, 19]
# Finding the length of the list
size = len(arr)
# Printing the given unsorted list
print('Unsorted List:')
printArray(arr)
# Calling bubbleSort() function
bubbleSort(arr, size)
# Printing the sorted list
print('Sorted List in Ascending Order:')
printArray(arr)


انتاج:

Unsorted List:
16 12 15 13 19
Sorted List in Ascending Order:
12 13 15 16 19

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

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

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

// C implementation of the
// optimised Bubble Sort algorithm
#include
#include
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j <(size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i printf('%d ', arr[i]);
}
printf(' ⁠n ');
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
printf('Unsorted Array: ⁠n');
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
printf('Sorted Array in Ascending Order: ⁠n');
printArray(arr, size);
return 0;
}

انتاج:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19

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

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

// JavaScript implementation of the
// optimised Bubble Sort algorithm
// Function to perform Bubble Sort
function bubbleSort(arr, size) {
// Loop to access each element of the array
for(let i=0; i // Variable to check if swapping occurs
var swapped = false;
// loop to compare two adjacent elements of the array
for(let j=0; j // Comparing two adjacent array elements
if(arr[j] > arr[j+1]) {
// Swap both elements if they're
// not in correct order
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
}
// Prints the elements of the array
function printArray(arr, size) {
for (let i=0; i document.write(arr[i] + ' ');
}
document.write('
')
}

var arr = [16, 12, 15, 13, 19];
// Finding the length of the array
var size = arr.length;
// Printing the given unsorted array
document.write('Unsorted Array:
');
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
document.write('Sorted Array in Ascending Order:
');
printArray(arr, size);


انتاج:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 15 13 16 19

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

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

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

يشارك يشارك سقسقة بريد الالكتروني كيف تبدأ مع Python باستخدام البرنامج النصي 'Hello World'

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

اقرأ التالي مواضيع ذات صلة

• برمجة
• جافا
• بايثون
• دروس الترميز

نبذة عن الكاتب يوفراج شاندرا(تم نشر 60 مقالاً)

يوفراج طالب جامعي في علوم الكمبيوتر بجامعة دلهي بالهند. إنه متحمس لتطوير الويب Full Stack. عندما لا يكتب ، فإنه يستكشف عمق التقنيات المختلفة.

تطبيقات الواقع الافتراضي للأندرويد مجانًا

المزيد من Yuvraj Chandra

اشترك في نشرتنا الإخبارية

انضم إلى النشرة الإخبارية لدينا للحصول على نصائح تقنية ومراجعات وكتب إلكترونية مجانية وصفقات حصرية!

انقر هنا للاشتراك