Skip to content
Shameem's Note
Shameem Reza JavaScript, WordPress & SwiftUI
Shameem's Note

JavaScript, WordPress & SwiftUI

BUY ME A COFFEE
  • Home
  • About
  • Now
Shameem's Note

JavaScript, WordPress & SwiftUI

June 21, 2017January 26, 2023

সর্টিংঃ বাবল সর্ট অ্যালগরিদম

সর্টিং মানেই যে কোন কিছু সাজানো, তা আমরা কম বেশি সবাই জানি। কম্পিউটার সায়েন্সের একটি গুরুত্বপূর্ণ বিষয় হচ্ছে অ্যালগরিদম, আর এই অ্যালগরিদমের মধ্যে সর্টিং অনেক গুরুত্বপূর্ণ একটি অংশ।

যতগুলো সর্টিং অ্যালগরিদম আছে, তার মধ্যে আমাদের কাছে সিলেকশন সর্টিং সহজ মনে হলেও, অনেকের কাছেই এই বাবল সর্ট (Bubble Sort) অনেক সহজ মনে হয়। আসলে সহজ মনে হবারই কথা, কেননা বাবল সর্ট অ্যালগরিদম আসলেই অনেক সহজ একটি সর্টিং অ্যালগরিদম।

বাবল সর্ট অ্যালগরিদম আমার কাছে বেশ মজা লাগে। তুমি প্রথম থেকে শেষ পর্যন্ত পাশাপাশি দুটি দুটি করে সংখ্যা নিতে থাকো, যদি দেখো আগের সংখ্যা পরের সংখ্যা থেকে বোড়, তাহলে অদলবদল করো। এই কাজ তোমাকে n সংখ্যক বার করতে হবে, কেননা বাবল সর্ট অ্যালগরিদম কিন্তু Ο(n2) সময় লাগাবে।

বাবল সর্ট অ্যালগরিদমে Ο(n2) সময় লাগে, এর কারণ হচ্ছে প্রথম বার যখন তুমি বাম থেকে ডানে যাবে, তখন সবচেয়ে বড়টি অবশয়ই একদম ডান মাথায় গিয়ে পৌঁছাবে। পরের বার দ্বিতীয় বড়টি ঠিক জায়গায় যাবে, এভাবে প্রতিবার একোটি একোটি করে সংখ্যা সঠিক স্থানে যাবে। তাই n বার এই কাজ করলে সব সংখ্যা সঠিক জায়গায় চলে যাবে।

বাবল সর্ট কিভাবে কাজ করে?

বাবল সর্ট অ্যালগরিদম কিভাবে কাজ করে তা বোঝার জন্য চলো প্রথমেই একোতি আনসর্টেড অ্যারে নেওয়া যাক। যাহেতু বাবল সর্ট Ο(n2) সময় নেই, তাই চেস্টা করবো যত ছোট বা কম ডেটা নেওয়া যায়।

বাবল সর্ট শুরু হয় প্রথম দুটি আইতেমের মধ্যে তুলনার মাধ্যমে। আর এই তুলনার মাধ্যমে খুজে বের করা হয় সব থেকে বড় আইটেম।

আমাদের নেওয়া অ্যারেতে শুরুতেই আছে ১৪ এবং ৩৩। যেহেতু ৩৩, ১৪ থেকে বড় তাই এখানে আগে থেকেই সর্টেড আছে, অর্থাৎ কোন পরিবর্তন হবে না। এখন আমাদেরকে ৩৩ এবং ২৭ এর মধ্যে তুলনা করে দকেহতে হবে কে বড়, আর কে ছোট।

এখানে আমরা দেখছি যে, ২৭ থেকে ৩৩ বড়, আর এই কারনেই ভ্যালু দুটি অদলবদল করতে হবে।

অদলবদলের পর আমাদের অ্যারে দেখতে হবে এমনঃ

এবার আমরা যদি ৩৩ এবং ৩৫ এর মধ্যে তুলনা করি, তাহলে দকেহব যে এরা আগে থেকেই সর্টেড আছে, কেননা ৩৫ তো ৩৩ থেকে বড়ই।

তারপর আবার আমরা পরের দুটি ভ্যালু এর মধ্যে তুলনা করবো, আর এক্ষেত্রে আমার ভ্যালু হচ্ছে ১০ এবং ৩৫।

আমরা সবাই জানি যে ৩৫ থেকে ১০ অনেক ছোট একোটি সংখ্যা, এর মানে সংখ্যা দুটি আমাদের এই অ্যারেতে সর্টেড নেই।

এখন বাবল সর্টের নিয়ম অনুযায়ী ভ্যালু দুটির অবস্থান অদলবদল করতে হবে, মানে ১০ কে নিয়ে আসতে হবে ৩৫ এর স্থানে। এভাবে আমাদের প্রথম ধাপ শেষ করার পর অ্যারে দেখতে হবে অনেকটা নিচের মতঃ

এবার তোমাকে আবার প্রথম থেকে শুরু করে দ্বিতীয় ধাপ কমপ্লিট করতে হবে, আর তখন আমাদের অ্যারে হবে এই রকমঃ

তুমি খেয়াল করেছ কি না জানি না। আমরা প্রতিবার বাবল সর্ট অ্যাপ্লাই করার পর, যে কোন একটি সংখ্যা সবার শেষে চলে যাচ্ছে। অর্থাৎ শুরুর দিকে ছোট সংখ্যা গুলো আনসর্টেড থাকলেও শেষের দিকে বোড় সংখ্যা গুলো কিন্তু ঠিকই সর্টেড আছে।

এবার আবারো আমরা তৃতীয় বারের জন্য বাবল সর্ট অ্যাপ্লাই করবো, কেননা আমাদের অ্যারে এখনো পুরোপুরি সর্টেড হয়নি।

এভাবে একোটির পর একটি সর্ট করার পর যখন আর অদলবদল করার জায়গা থাকবে না, তখন আমাদের অ্যারে দেখবে হবে নিচের মতঃ

এখানে মনে রাখতে হবে যে, আমরা বাবল সর্ট ততক্ষন চালাতে থাকবো, যতক্ষন পুরপুরি সর্তেড লিস্ট পাবো।

আশাকরি বাবল সর্ত এখন তোমার কাছে অন্যদের মতই অনেক সহজ মনে হচ্ছে। তবে আমার কাছে কিন্তু ঐ সিলেকশন সর্ট অ্যালগরিদমই সহজ লাগে। 🙂

আচ্ছা, এবার তাহলে বাবল সর্ট অ্যালগরিদম দেখে চেষ্টা ক্র পুরোপুরি বুঝেছো কি না?

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

বাবল সর্ট তুমি চাইলে যে কোন ল্যাঙ্গুয়েজ দিয়েই ইমপ্লিমেন্ট করতে পারো, কেননা এটা ইমপ্লিমেন্ট করা খুব সহজ। নিচে যে কোড দিয়েছি, তুমি চাইলে এই কোডে কিছু অপটিমাইজেশন করতে পারো। যেমনঃ এমন হতে পারে যে n বারের আগেই অ্যারেটি সর্টেড হয়ে গেছে, সে ক্ষেত্রে তুমি আগেই লু থেকে বের হয়ে যেতে পারো।

আবার প্রতিবার তোমার সব জোড় সংখ্যা যাচাই করার দরকার নেই, কারণ i সংখ্যকবার চললে তুমি জানবে যে i টি সংখ্যা ঠিক জায়গায় চলে গেছে। তুমি এভাবে কিছু অপটিমাইজেশন করতে পারো, কিন্তু যতই অপটিমাইজেশন করো কেন, এই অ্যালগরিদমের worst কেইস এ Ο(n2) সময় লাগবেই। আচ্ছা তোমরা কি কেউ সেই worst কেইস্টি বের করতে পারবে?

সহজ কোডঃ

for(i=1; i<=n; i++)
{
	for (j=1; j num[j])
		{
		temp=num[j];
		num[j] = num[j+1];
		num[j+1] = temp;
		}
}

সি দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ

// C program for implementation of Bubble sort
#include 
 
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)
{
    for (int 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;
}

আউটপুরঃ Sorted array: 11 12 22 25 34 64 90

পাইথন দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ

# Python program for implementation of Bubble Sort
 
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]),

আউটপুটঃ Sorted array: 11 12 22 25 34 64 90

জাভাস্ক্রিপ্ট দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ

var arr = [5,6,3,1,2,4];  
  
bubbleSortAlgo(arr);  
  
function bubbleSortAlgo(arr){  
    for(var i=0;iarr[j+1]){  
                var tempValue= arr[j];  
                arr[j]=arr[j+1];  
                arr[j+1]=tempValue;  
                flag=true;  
            }  
        }  
        if(flag==false)  
        break;  
    }  
    console.log("Sorted array: ");  
    console.log(arr);  
}  

আউটপুটঃ Sorted array: 1,2,3,4,5,6

আশাকরি বাবল সর্ট অ্যালগরিদম কি, কিভাবে কাজ করে, কিভাবে ইমপ্লিমেন্ট করতে হয়, তা তুমি ভালো করেই বুঝেছো। আর যদি না বুঝো তবে পুরো লেখা আরো কএয়কবার পড়ো, বিশেষ করে উদাহরণের অংশটুকু।

তুমি যদি ইনসার্শন সর্টিং ভালো করে বুঝতে চাও, তাহলে আমার ইনসার্শন সর্ট পোস্ট পড়তে পারো।

Bangla

Post navigation

Previous post
Next post

Woth to read

Bangla সিলেকশন সর্ট

সর্টিংঃ সিলেকশন সর্ট

June 21, 2017November 4, 2021

সর্টিং অ্যালগোরিদমের মুল কাজই হচ্ছে অ্যারেতে থাকা দুটি উপাদানের অবস্থান সোয়াপ(swap) বা বিনিময় করা। সিলেকশন…

Read More
Bangla ফ্র্যাকশনাল ন্যাপস্যাক সমস্যা

ফ্র্যাকশনাল ন্যাপস্যাক সমস্যা

June 25, 2017October 15, 2019

গ্রীড অ্যালগরিদমের জন্য ফ্র্যাকশনাল ন্যাপস্যাক (Fractional Knapsack) খুব পরিচিত একটি সমস্যা। অনেকের কাছে এই অ্যালগরিদম…

Read More
Bangla সিএসএস টাইপিং ইফেক্ট তৈরি

সিএসএস টাইপিং ইফেক্ট তৈরি

July 4, 2017October 15, 2019

কাজে বা বিনা কাজে তুমি বিভিন্ন ওয়েব সাইট ঘুরে ঘুরে দেখছো। এমনি সময় পরার এক…

Read More

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Shameem Reza

I am the Father of a son, blessed with a pious wife. I am a self-taught iOS developer, SwiftUI Addicted and WordPress Ninja.

Over 80,000+ Readers

Get fresh content from Shameem.

  • Twitter
  • GitHub
  • LinkedIn
SwiftUI
JavaScript
Wordpress
Tips & Tricks

Recommended Resources

WordHero: 50+ AI writing tool to write sales and marketing emails that sell.

Rytr: AI Writing Tool to generate high-quality content.

WriterZen: Boost SEO rankings with tools organized into a results-oriented workflow.

WP 301 Redirects: Improve SEO and customer experience by finding broken links, site redirects, and 404 errors.

Join 3500+ Developers Getting Early Access To My Posts!

I learned these in the past 10 years by building a digital product development agency, and dozens of different web & mobile applications for clients and myself. Sign up to get updates when I write something new. No spam ever.

© 2023 Shameem's Note | Contact - Privacy - Disclosure