বাবল সর্ট(Bubble sort) অ্যালগরিদম

 

গত পর্বে আমি সিলেকশন সর্ট(Selection sort) অ্যালগরিদম নিয়ে আলোচনা করেছিলাম এই পর্বে আরও একটি সহজ সর্টিং অ্যালগরিদম নিয়ে আলোচনা করবো নাম বাবল সর্ট(Bubble sort) ।

কম্পিউটার সায়েন্সে যতগুলো সর্টিং অ্যালগরিদম রয়েছে তার-মধ্যে সবচেয়ে সহজ অ্যালগরিদম বলা হয় বাবল সর্ট কে । তো চলুন আজাইরা ইন্ট্রো গল্প বাদ দিয়ে বাবল সর্ট(Bubble sort) অ্যালগরিদম নিয়ে আলোচনা করা যাক ।

বাবল সর্ট(Bubble sort) অ্যালগরিদম :-

এই অ্যালগোরিদমের মূল বিষয় হলো, পরপর দুইটি উপাদানের মধ্যে তুলনা করে তাদের ক্রম অনুসারে রাখা । যেমন : - নিচের visualization টি লক্ষ্য করি :-

ধরি, আমার কাছে একটি অ্যারে আছে [400,200,100,300] । এখন এই অ্যারেটি আমি বাবল সর্ট(Bubble sort) অ্যালগরিদম ব্যাবহার করে ছোট থেকে বড় ক্রমে অর্থাৎ Ascending Order এ সাজাতে চাই ।

উপরোক্ত অ্যারেতে মোট ৪টি উপাদান বাঁ সংখ্যা আছে । আপনি চাইলে যেকোনো সাইজের অ্যারে নিয়ে কাজ করতে পারবেন আমার সময় বাঁচানোর জন্য আমি কম সংখ্যক উপাদানসুমহের অ্যারেটি নিলাম । চলুন কাজে আসা যাক -

স্টেপ(০১) :- প্রথমে আমি অ্যারের প্রথম ২টি উপাদান নিবো সেক্ষেত্রে উপাদানগুল হলো 400 ও 200 । এখন এই ২টি সংখ্যার মধ্যে আমি তুলনা করবো যে সংখ্যাটি ছোট তাকে প্রথমে এবং বড় সংখ্যাটিকে তার পরে রাখবো । যেহেতু, 200 ছোট তাই 200 কে প্রথমে এবং 400 কে তার পরে রাখলাম এখন অ্যারেটি হবে -

[200,400,100,300]

স্টেপ(০২) :- এবার 400 এবং 100 এর তুলনা করবো সেক্ষেত্রে ছোট সংখ্যাটি 100 এবং বড় সংখ্যাটি 400 । তাহলে 100 কে আগে এবং 400 কে পরে রাখলাম -

[200,100,400,300]

স্টেপ(০৩) :- এবারে 400 এবং 300 এর মধ্যে তুলনা করি । 400 > 300 এক্ষেত্রে 300 ছোট এবং 400 বড় তাহলে 300 কে প্রথমে 400 কে পরে রাখি -

 [200,100,300,400]

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

স্টেপ(০৪) :- 200 এবং 100 এর মধ্যে তুলনা করি এক্ষেত্রে 100 ছোট এবং 200 বড় সংখ্যা । তাহলে 100 কে প্রথমে এবং 200 কে তার পরের স্থানে রাখি -

 [100,200,300,400]

স্টেপ(০৫):-  200 ও 300 এর মধ্যে যদি তুলনা করি তাহলে 200 হবে ছোট এবং 300 হবে বড় সংখ্যা । এখন এদের স্থানের অদল-বদল করতে হবে অর্থাৎ 200 কে আগে এবং 300 কে পরের স্থানে রাখতে হবে কিন্তু অ্যারের দিকে লক্ষ করলে দেখতে পারবো যে 200 এবং 300 তাদের যথাযথ স্থানেই রয়েছে । 

 

[100,200,300,400]

স্টেপ(০৬) :- 100 ও 200 এর মাঝে তুলনা করি স্পষ্ট দেখতে পাচ্ছি 100 ও 200 তাদের যথাযথ স্থানেই রয়েছে । সাথে বাকি সংখ্যাগুলোও কিন্তু ঠিকঠাক স্থানেই রয়েছে । এ পর্যায়ে এসে বলতে পারি আমাদের অ্যারেটি সর্টেড অর্থাৎ ছোট থেকে বড় ক্রমে সাজানো আছে ।

 আশা করি, আপনারা বাবল সর্ট(Bubble sort) অ্যালগরিদম বুঝতে পেরেছেন যদি একবারে বুঝে না থাকেন তাহলে আরেকবার পড়তে হবে । চলুন এখন ইমপ্লিমেন্টেশন বাঁ কোড লিখা যাক -

In Python :-

def bubbleSort(arr):
    # i এর মান  0 থেকে len(arr) এর আগ পর্যন্ত ১ করে বাড়াই
    for i in range(len(arr)):

        # j এর মান 0 থেকে len(arr)-i-1 এর আগ পর্যন্ত ১ করে বাড়াই
        for j in range(0, len(arr) - i - 1):

            # arr[j] > arr[j+1] সত্য হয় তাহলে দুইটিকে অদল-বদল করি

            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

In JavaScript :-

const optimizedBubbleSort = (arr) => {
  // i এর মান  0 থেকে arr.length এর আগ পর্যন্ত ১ করে বাড়াই
  for (let i = 0; i < arr.length; i++) {
    // j এর মান 0 থেকে arr.length-i-1 এর আগ পর্যন্ত ১ করে বাড়াই
    for (let j = 0; j < arr.length - i - 1; j++) {
      // arr[j] > arr[j+1] সত্য হয় তাহলে দুইটিকে অদল-বদল করি
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
};

যেকোনো অ্যালগরিদম বাঁ ডেটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই ইমপ্লিমেন্ট করতে পারবেন ।

চলুন বাবল সর্ট(Bubble sort) অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি বের করা যাক -

টাইম কমপ্লেক্সিটি(Time Complexity) :

উপরোক্ত কোড লক্ষ করলে দেখবো প্রথম লুপটি চলে i = 0 থেকে n পর্যন্ত । এবং ভেতরের অর্থাৎ ২য় লুপটি চলে j = 0 থেকে n-i-1 পর্যন্ত ।

• যখন i = 0, তখন ভেতরের লুপটি চলে j = 0 থেকে j = n - i - 1 অর্থাৎ 3 বার ।

• আবার i = 1 হলে, ভেতরের লুপটি চলে j = 1 থেকে j = n - i - 1 অর্থাৎ 2 বার ।

এভাবেই যতক্ষণ না লুপটি শেষ হয় চলতেই থাকবে ।

এখন আমরা খুব সহজেই বলে দিতে পারি যে, উক্ত প্রোগ্রামের টাইম কমপ্লেক্সিটি(Time Complexity) O(n*(n-i-1)) 

অর্থাৎ O(n*(n-1)) ।

=> n*(n - 1)

=> n² - n

=> O(n² - n)

O(n² - n) কে আমরা O(n²) লিখতে পারি কারণ n² এর তুলনায় n ছোট ।

স্পেস কমপ্লেক্সিটি(Space Complexity) :

উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?

আশা করি পেরেছেন হ্যাঁ স্পেস কমপ্লেক্সিটি(Space Complexity) হচ্ছে - O(1) ।

ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে নিতেই পারি বাবল সর্ট(Bubble sort) অ্যালগরিদম সম্পর্কে ভালো একটা দখল চলে আসছে ।

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Ascending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজিয়েছি এখন আপনি বাবল সর্ট(Bubble sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Descending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজানোর চেষ্টা করবেন । 

খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো ।