বাবল সর্ট(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 অর্থাৎ বড় থেকে ছোট ক্রমে সাজানোর চেষ্টা করবেন । 

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

Bubble Sort - Wikipedia

Read More

সিলেকশন সর্ট(Selection sort) অ্যালগরিদম

কোনো উপাদান বাঁ ডাটাসমূহকে একটি নির্দিষ্ট ক্রমে সাজানোর প্রক্রিয়াই হলো সর্টিং(Sorting) । সর্টিং(Sorting) আমরা দুই ভাবে করতে পারি -

 ১। Ascending Order

  এবং 

২। Descending Order

১। Ascending Order :-

ছোট থেকে বড় ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Ascending Order । যেমন :-

• শ্রেণিকক্ষের হাজিরা খাতায় শিক্ষার্থীদের নামগুলো রোল নম্বর অনুযায়ী সাজানো থাকে ।

২। Descending Order :-

বড় থেকে ছোট ক্রমে সাজানোর প্রক্রিয়াকে বলা হয় Descending Order । যেমন :-

• ফাইনাল পরীক্ষা শেষে রেজাল্ট শিটে শিক্ষার্থীদের নামগুলো মোট নম্বর অনুযায়ী বড় থেকে ছোট ক্রমে সাজানো থাকে ।

আসল কথায় আসা যাক, প্রোগ্রামিং করার সময় বিভিন্ন কাজে ডাটাসমূহকে এরকম সর্ট করার প্রয়োজন হয় । তখন আমরা খুব সহজেই বিভিন্ন সর্টিং অ্যালগরিদম ব্যাবহার করে ডাটাসমূকে সর্ট করে ফেলতে পারি । কম্পিউটার সায়েন্সে অনেক ধরণের সর্টিং অ্যালগরিদম আছে তারমধ্যে সহজ এবং জনপ্রিয় একটি সর্টিং অ্যালগরিদম হইলো সিলেকশন সর্ট(Selection sort) ।

সিলেকশন সর্ট(Selection sort) :-

এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো, প্রতি ইটারেশনে ডাটাসমূহ থেকে একটি সঠিক উপাদানকে সিলেক্ট করা এবং তাকে অন্য আরেকটি উপাদানের সাথে অদল-বদল করে(যদি প্রয়োজন হয়) সঠিক জায়গায় এসাইন করা ।

নিচে  সিলেকশন সর্ট(Selection sort) এর  Visualization লক্ষ্য করুন :-

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

স্টেপ(১) :- প্রথমে উপরোক্ত অ্যারে থেকে সবচেয়ে বড় সংখ্যাটিকে সিলেক্ট করি এক্ষেত্রে 600 হচ্ছে সবচেয়ে বড় সংখ্যা । এখন 600 কে সবার প্রথমে নিয়ে আসতে হবে এজন্য অ্যারের প্রথম উপাদান 100 এর সঙ্গে 600 এর স্থান অদল-বদল করি । অদল-বদল শেষে আমাদের অ্যারেটি দাঁড়াবে এরকম -

[600,400,300,100,500]

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

[600,500,300,100,400]

স্টেপ(৩) :- অ্যারের প্রথম দুটি উপাদান সর্ট করা শেষ এখন বাকি তিনটি(300,100,400) উপাদান সর্ট করতে হবে । তাহলে এই তিনটি উপাদানের মধ্যে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি সংখ্যাটি হলো 400 । এরপর 300 এর সাথে 400 এর স্থান অদল-বদল করি এখন অ্যারেটি হবে -

[600,500,400,100,300]

স্টেপ(৪) :- এখন আমরা নিশ্চিত যে, অ্যারের প্রথম ৩টি উপাদান সর্টেড রয়েছে তাহলে বাকি ২টি(100,300) উপাদান থেকে সবচেয়ে বড় সংখ্যাটি সিলেক্ট করি এক্ষেত্রে সংখ্যাটি হচ্ছে 300 । এখন 100 এর সাথে 300 এর স্থান অদল-বদল করি । অদল-বদল শেষে অ্যারেটি হবে -

[600,500,400,300,100]

যেহেতু, অ্যারের ৫টি উপাদানের মধ্যে প্রথম ৪টি উপাদান বড় থেকে ছোট ক্রমে সাজানো । সেক্ষেত্রে আমরা নিশ্চিত যে, অ্যারের শেষ উপাদান অর্থাৎ 100 তার সঠিক জায়গাতেই আছে এর কোনো অদল-বদল করতে হবে নাহ । তাহলে আমাদের ফাইনাল অর্থাৎ সর্টেড অ্যারেটি হলো -

[600,500,400,300,100]

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

পাইথনে ইমপ্লিমেন্টেশন :-

def selectionSort(arr):
    # i এর মান  0 থেকে len(arr) - 1 এর আগ পর্যন্ত ১ করে বাড়াই
    for i in range(len(arr) - 1):
        # largest নামে variable নিই এবং i এসাইন করি
        largest = i

        # j এর মান i+1 থেকে len(arr) এর পর্যন্ত ১ করে বাড়াই

        for j in range(i+1, len(arr)):

          # arr[largest] < arr[j] যদি সত্য হয় তাহলে largest এসাইন করি
            if arr[largest] < arr[j]:
                largest = j

        # যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
    return arr

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন :-

const selectionSort = (arr) => {
  // i এর মান  0 থেকে arr.length - 1 এর আগ পর্যন্ত ১ করে বাড়াই
  for (let i = 0; i < arr.length - 1; i++) {
    // largest নামে variable নিই এবং i এসাইন করি
    let largest = i;
    // j এর মান i+1 থেকে arr.length এর পর্যন্ত ১ করে বাড়াই
    for (let j = i + 1; j < arr.length; j++) {

      // arr[largest] < arr[j] যদি true হয় তাহলে largest এ j এসাইন করি

      if (arr[largest] < arr[j]) {
        largest = j;
      }
    }

    // যদি largest এবং i সমান না হয় তাহলে সংখ্যা দুইটি অদল-বদল করি
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
    }
  }
  return arr;
};

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

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

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

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

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

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

• i = 2 হলে, ভেতরের লুপটি চলে j = 2 থেকে j = n - 1 অর্থাৎ 2 বার । এভাবেই যতক্ষণ না লুপটি শেষ হয় চলতেই থাকবে ।

একটু লক্ষ করলে দেখতে পারবো যে, প্রথম লুপটি n সংখ্যক বার চললে তার ভেতরের লুপটি চলতেছে m সংখ্যক বার । তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) দাঁড়াবে O(n *  m) । এখানে যেহেতু m এর মান n এর সমান তাহলে টাইম কমপ্লেক্সিটি(Time Complexity) বলতে পারি O(n  * n) বা O(n²) ।

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

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

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

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

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

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

---

Read More

চেক প্যালিনড্রোম (Palindrome) - using Stack

 

আমি বেশ কিছুদিন আগে Stack এবং Queue ডাটা-স্ট্রাকচার নিয়ে আলোচনা করেছিলাম সাথে জাভাস্ক্রিপ্ট এবং পাইথন দিয়ে ইমপ্লিমেন্টও করেছিলাম । তো আজকে আমি, একটি সুপরিচিত এবং সহজ প্রব্লেম নিয়ে আলোচনা করবো এবং Stack ডাটা-স্ট্রাকচার দিয়ে সমাধান করবো ।

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

• Stack ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Queue ডাটা-স্ট্রাকচার ইন জাভাস্ক্রিপ্ট
• Stack ডাটা-স্ট্রাকচার ইন পাইথন
• Queue ডাটা-স্ট্রাকচার ইন পাইথন

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি স্ট্রিং নিবে । যদি স্ট্রিং টি Palindrome হয় তাহলে true নতুবা false রিটার্ন করবে ।

Palindrome String :-

যদি কোনো স্ট্রিং ডানে এবং বামে অর্থাৎ উভয় থেকে একই হয় তাহলে তাকে Palindrome String বলা যায় । যেমন :- mam, madam, racecar ইত্যাদি ।

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি আবার এক লাইনেও সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি স্ট্রিং আছে "MaM" । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, "MaM" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "M" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "M" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["M"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "a" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["M", "a"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "M" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["M", "a", "M"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "M" 

contains = ["M", "a"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "Ma" 

contains = ["M"]

এখন,  contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "MaM" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার এবং word এর মান একই সেহেতু "MaM" একটি Palindrome স্ট্রিং ।

আরেকটি উদাহরণ :-

ধরি আমাদের কাছে একটি str নামে স্ট্রিং আছে,

 str = "abc" ।

স্টেপ(০১) :- প্রথমে, "abc" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "a" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "a" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["a"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "b" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["a", "b"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "c" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["a", "b", "c"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো, যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে - 

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "c" 

contains = ["a", "b"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cb" 

contains = ["a"]

এখন, contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cba" 

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার ছিলো "abc" এবং word এর মান "cba" সেহেতু "abc" একটি Palindrome স্ট্রিং নয়।

তো চলুন এখন কোড লিখা যাক -

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const isPalindrome = (str) => {
  let contains = [];
  for (let i = 0; i < str.length; i++) {
    contains.push(str[i]);
  }

  let word = "";
  while (contains.length > 0) {
    word += contains.pop();
  }
  return word === str;
};

Output :

isPalindrome("MaM");  // true
isPalindrome("abc"); // false

পাইথনে ইমপ্লিমেন্টেশন :-

def isPalindrome(str):
    contains = []
    for item in str:
        contains.append(item)

    word = ""
    while len(contains) > 0:
        word += contains.pop()

    return word == str

Output :

isPalindrome("MaM"); # True
isPalindrome("abc"); # False

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, স্ট্রিং এ লুপ থ্রু করেছি এবং প্রত্যেকতা উপাদানকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি ।

word নামে একটি ফাকা স্ট্রিং নিয়েছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে word এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে যোগ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হবে । তখন যদি word এবং str সমান হয় তাহলে funciton টি আমাদেরকে true রিটার্ন করবে নতুবা false রিটার্ন করবে ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।

Read More