Bubble Sort একটি সহজ এবং মৌলিক সর্টিং অ্যালগরিদম। এটি তালিকার প্রতিটি উপাদানকে একে একে তুলনা করে এবং যদি দুটি পরস্পরের থেকে বড় হয় তবে তাদের স্থান পরিবর্তন করে। এই প্রক্রিয়া চলতে থাকে যতক্ষণ না সমস্ত উপাদান সাজানো হয়।
১. Bubble Sort এর ইমপ্লিমেন্টেশন
১.১ C প্রোগ্রামে Bubble Sort উদাহরণ
#include <stdio.h>
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
১.২ কোড বিশ্লেষণ
bubbleSort ফাংশন:
- ইনপুট হিসেবে একটি অ্যারে এবং এর সাইজ গ্রহণ করে।
- প্রথম লুপ (
i) প্রতিটি পাসের জন্য নিয়ন্ত্রণ করে, এবং দ্বিতীয় লুপ (j) প্রতিটি উপাদানকে তুলনা করে। - যদি
arr[j]arr[j + 1]এর থেকে বড় হয়, তাহলে তাদের স্থান পরিবর্তন করে।
main ফাংশন:
- একটি নমুনা অ্যারে তৈরি করে এবং
bubbleSortফাংশন কল করে। - ফলস্বরূপ সাজানো অ্যারে প্রিন্ট করে।
২. Bubble Sort এর বিশ্লেষণ
২.১ সময় জটিলতা (Time Complexity)
Worst Case: O(n²)
(যখন তালিকা সম্পূর্ণরূপে বিপরীত ক্রমে সাজানো থাকে, প্রতিটি উপাদানকে তুলনা করতে হয়।)
Best Case: O(n)
(যখন তালিকা ইতিমধ্যেই সাজানো থাকে এবং শুধুমাত্র একটি পাস প্রয়োজন।)
Average Case: O(n²)
(গড় ক্ষেত্রে, প্রায় n² তুলনা করতে হয়।)
২.২ স্থান জটিলতা (Space Complexity)
- Space Complexity: O(1)
(Bubble Sort স্থান সঞ্চয় করে, কারণ এটি ইনপুট অ্যারে ছাড়া অতিরিক্ত স্থান ব্যবহার করে না।)
২.৩ কার্যকারিতা
- সহজতা: সহজ এবং বুঝতে সহজ।
- প্রয়োগ: ছোট তালিকার জন্য কার্যকর, কিন্তু বড় তালিকার জন্য কার্যকরী নয়।
২.৪ দুর্বলতা
- কম কার্যকরী: সময়ের দৃষ্টিকোণ থেকে এটি অন্যান্য সর্টিং অ্যালগরিদমের চেয়ে ধীর।
- অনেক তুলনা: প্রতিটি উপাদানকে তুলনা করতে হয়, তাই এর কার্যকারিতা কম।
Content added By
Read more
