ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম

 

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

ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম :-

এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো - একটি নির্দিষ্ট সংখ্যার জন্য এমন একটি জায়গা খুঁজে বের করা যেখানে সংখ্যাটিকে রাখলে তার আগের সংখ্যাটি তার থেকে ছোট বা সমান হবে এবং পরের সংখ্যাটি তার থেকে বড় হবে । তবে সংখ্যাটি যদি অ্যাঁরে বা লিস্টের সবচেয়ে ছোট বা বড় সংখ্যা হয় তাহলে তার জন্য সবার প্রথমে জায়গা করে দিতে হবে ।যেমন : - নিচের visualization টি লক্ষ্য করি :-

 

ধরি, আমাদের কাছে [10,30,40] এই অ্যাঁরেটি ছোট থেকে বড় ক্রমে সাজানো আছে । আমি এই অ্যাঁরেতে আরেকটি সংখ্যা যুক্ত করতে চাই সংখ্যাটি হলো 20 । এখন আমাকে 20 কে এমন এক জায়গায় বসাতে হবে যেখানে তার আগের সংখ্যা তার থেকে ছোট বা সমান হবে এবং তার পরের সংখ্যাটি তার থেকে বড় হবে ।

যদি অ্যাঁরেতে লক্ষ করি তাহলে দেখতে পারবো যে, সেই কাঙ্খিত জায়গাটি হচ্ছে 10 এর পরের অবস্থান কারণ, 20 থেকে 10 ছোট এবং 30 বড় । এখন যেহেতু 10 এর পরের অবস্থানে 30 আছে, তাহলে 30 এর জায়গায় 20 কে বসাতে হলে অ্যাঁরের শেষ থেকে অর্থাৎ 40 কে এক ঘর ডানে সরাতে হবে এখন 40 যেখানে ছিলো সেই ঘরটি কিন্তু ফাকা -

[10, 30, _, 40]

এরপর 30 কে এক ঘর ডানে সরাই - [10, _, 30, 40]

এখন ফাকা জায়গাটি কিন্তু 20 এর জন্য পারফেক্ট জায়গা অর্থাৎ, যে স্থানটি ফাকা তার আগের সংখ্যাটি 20 থেকে ছোট এবং পরের সংখ্যাটি 20 থেকে বড় । তাহলে ফাকা জায়গাটিতে 20 কে এসাইন করি -

[10, 20, 30, 40]

এতক্ষণ যে পদ্ধতিতে একটি সংখ্যা অ্যাঁরেতে সাজানো হলো এই পদ্ধতিকেই আমরা ইনসারশন সর্ট(Insertion sort) বলতে পারি ।

অ্যারে(Array) ও ইনসার্শন সর্ট(Insertion sort) -

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

 

[50, 20, 10, 30]

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

[20, 50, 10, 30]

স্টেপ(০২) :- 50 এবং 10 এর মধ্যে 10 এর জন্য উপযুক্ত জায়গা খুঁজে বের করি । এক্ষেত্রে, অ্যারের প্রথমে 10 কে রাখতে হবে অর্থাৎ 20 এর অবস্থানে । তাই, প্রথমে 50 কে এক ঘর ডান দিকে সরাই - [20, _, 50, 30]

এখনও উক্ত ফাকা স্থানটি কিন্তু 10 এর উপযুক্ত জায়গা না তাই 20 কেও এক ঘর ডান দিকে সরাই - [_, 20, 50, 30] এখন ফাকা স্থানে অর্থাৎ 20 এর আগের ঘরে 10 এসাইন করি -

[10, 20, 50, 30]

স্টেপ(০৩) :- 50 এবং 30 এর মধ্যে 30 এর জন্য উপযুক্ত জায়গা খুঁজে বের করি এক্ষেত্রে, 20 এবং 50 এর মাঝে । তাই 50 কে এক ঘর ডানদিকে সরাই -

[10, 20, _, 50] এখন ফাকা জায়গাটিতে 30 কে এসাইন করি -

 

[10, 20, 30, 50]

ব্যাস, উপরোক্ত অ্যারে বা লিস্টটি ছোট থেকে বড় ক্রমে অর্থাৎ Accending order এ সাজানো হয়ে গেলো । এখন আপনি যদি বুঝতে না পারেন তাহলে খাতা-কলম নিয়ে বিষয়টি বোঝার চেষ্টা করতে পারেন । যদি প্রথম বা দ্বিতীয় বারে বিষয়টি বুঝে থাকেন তাহলে আপনি একটি বড় অ্যারে বা লিস্টকে খাতা-কলমে সর্ট করতে পারেন । তো চলুন এখন ইমপ্লিমেন্টেশন করা যাক -

In Python : 

def insertionSort(arr):
    for i in range(1, len(arr)):
        # arr[i] কে currentValue তে এসাইন করি
        currentValue = arr[i]
        # currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করি
        j = i - 1
        # যদি j, 0 থেকে সমান বা বড় হয় এবং  arr[j] থেকে currentValue ছোট হয়
        while j >= 0 and arr[j] > currentValue:
            # arr[j] কে তার পরের ঘরে রেখে দিই
            arr[j+1] = arr[j]
            # j এর মান 1 করে কমাই
            j -= 1
        # এখন খালি জায়গায় currentValue কে বসাই
        arr[j+1] = currentValue
    return arr

 

In JavaScript :

function insertionSort(arr) {
  // একটি currentValue নামে ভেরিয়েবল নিই
  var currentValue;
  // i এর মান 1 থেকে len(arr) এর আগ পর্যন্ত 1 করে বাড়াই
  for (var i = 1; i < arr.length; i++) {
    // arr[i] কে currentValue তে এসাইন করি
    currentValue = arr[i];
    // currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করি (j = i - 1)
    // যদি j, 0 থেকে সমান বা বড় হয় এবং  arr[j] থেকে currentValue ছোট হয়
    for (var j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      // arr[j] কে তার পরের ঘরে রেখে দিই
      arr[j + 1] = arr[j];
    }
    // এখন খালি জায়গায় currentValue কে বসাই
    arr[j + 1] = currentValue;
  }
  return arr;
}

আপনি চাইলে জাভাস্ক্রিপ্ট কোডে for লুপের পরিবর্তে while লুপ ব্যাবহার করতে পারেন ।

উপরোক্ত কোড বিশ্লেষণ :-

উপরের প্রোগ্রামে, প্রথমে i=1 থেকে অ্যারের লেন্থ পর্যন্ত লুপ চালিয়েছি । তারপর currentValue নামে একটি ভেরিয়েবলের মাঝে অ্যারের Present ভ্যালুকে রাখছি । এক্ষেত্রে কারেন্ট ভ্যালুটি যাতে হারিয়ে না যায় তা নিশ্চিত করছি কারণ পরবর্তীতে এই currentValue কেই তার যথাযথ স্থানে রাখতে হবে ।

তারপর ভেতরের লুপে j >= 0 এবং arr[j] > currentValue এইভাবে চেক করতেছি । এখানে, যদি j এর মান 0 থেকে ছোট হয় তাহলে আমি বুঝতে পারবো যে অ্যারে বা লিস্টের সব উপাদানই currentValue থেকে বড় । আবার, j এর মান যদি 0 থেকে বড় বা সমান হয় তাহলে দ্বিতীয় শর্তপরীক্ষা করা করবো অর্থাৎ arr[j] > currentValue ।

এখন যদি দ্বিতীয় শর্ত অর্থাৎ arr[j] > currentValue সত্য হয় তাহলে, arr[j] কে আমরা এক ঘর ডানে সরিয়ে দিব - arr[j + 1] = arr[j]

আবার, arr[j] > currentValue যদি মিথ্যা হয় তাহলে, লুপ থেকে বের হয়ে arr[j + 1] এ currentVal কে এসাইন করে দিব - arr[j + 1] = currentVal ইত্যাদি ।

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

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

উপরোক্ত কোড লক্ষ করলে আশা করি টাইম কমপ্লেক্সিটি(Time Complexity) বলে দিতে পারবেন । এই অ্যালগোরিদমেরও টাইম কমপ্লেক্সিটি(Time Complexity) O(n²) ।

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

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

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

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

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Accending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজিয়েছি এখন আপনি ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Decending 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