গিট ব্রাঞ্চিং সম্পর্কে বাংলায় বিস্তারিত

গিট ব্রাঞ্চিং বাংলায় বোঝা

গিট ব্রাঞ্চিং সম্পর্কে সহজে বোঝার জন্য বাংলায় বিস্তারিত গাইড।

গিট ব্রাঞ্চ কী?

ধরুন, আপনার একটা গাছ আছে। গাছের মূল ডালটা হলো main ব্রাঞ্চ। এখন আপনি যদি গাছের একটা নতুন ডাল বাড়াতে চান, যেখানে আপনি নতুন কিছু চেষ্টা করবেন, সেটাই হলো একটা নতুন "ব্রাঞ্চ"। এই নতুন ব্রাঞ্চে আপনি যা খুশি পরিবর্তন করতে পারেন, কিন্তু মূল ডাল অপরিবর্তিত থাকবে।

কেন ব্রাঞ্চ ব্যবহার করবেন?

• নতুন ফিচার যোগ করা: একটা নতুন ফিচার যোগ করতে চাইলে আলাদা ব্রাঞ্চে কাজ করুন।
• বাগ ফিক্স করা: সমস্যা ঠিক করতে আলাদা ব্রাঞ্চ ব্যবহার করুন।
• টিমে একসঙ্গে কাজ: অনেকে একসঙ্গে কাজ করলে প্রত্যেকে নিজের ব্রাঞ্চে কাজ করতে পারে।

কীভাবে ব্রাঞ্চ তৈরি করবেন?

১. বর্তমান ব্রাঞ্চ চেক করা

git branch

এটা দেখাবে আপনি কোন ব্রাঞ্চে আছেন।

২. নতুন ব্রাঞ্চ তৈরি করা

git branch feature-1

৩. নতুন ব্রাঞ্চে যাওয়া

git checkout feature-1

অথবা এক লাইনে:

git checkout -b feature-1

৪. কাজ করা এবং কমিট করা

git add .
git commit -m "নতুন ফিচার যোগ করা হয়েছে"

৫. মূল ব্রাঞ্চে মার্জ করা

git checkout main
git merge feature-1

৬. ব্রাঞ্চ ডিলিট করা

git branch -d feature-1

উদাহরণ

ধরুন, আপনার একটা ওয়েবসাইটে "লগইন" ফিচার যোগ করতে চান:

1. git checkout -b login-feature দিয়ে ব্রাঞ্চ তৈরি করুন।
2. কোড লিখুন এবং কমিট করুন।
3. git checkout main এবং git merge login-feature করুন।

সুবিধা

• মূল কোড নিরাপদ থাকে।
• একাধিক কাজ একসঙ্গে করা যায়।
• ভুল হলে ব্রাঞ্চ বাতিল করা যায়।

আরও জানতে আমাদের সাথে যোগাযোগ করুন।

Read More

adjacent_find() ফাংশনটি বাংলায় ব্যাখ্যা এবং সব ধরনের সম্ভাব্য উদাহরণ

C++ এর adjacent_find() ফাংশন - বাংলায় ব্যাখ্যা

লেখক: Shakil Babu | তারিখ: ২৯ মার্চ, ২০২৫

adjacent_find() কী?

C++ এর <algorithm> লাইব্রেরিতে adjacent_find() একটি ফাংশন যা কোনো রেঞ্জের (যেমন: ভেক্টর, অ্যারে) মধ্যে দুটি পাশাপাশি উপাদান খুঁজে বের করে, যারা একই মান ধারণ করে বা কোনো নির্দিষ্ট শর্ত পূরণ করে। এটি প্রথম জোড়া পাশাপাশি উপাদানের ইটারেটর রিটার্ন করে। যদি এমন কোনো জোড়া না পাওয়া যায়, তবে রেঞ্জের শেষ ইটারেটর রিটার্ন করে।

সিনট্যাক্স

adjacent_find (ForwardIterator first, ForwardIterator last);
// অথবা
adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

• first: রেঞ্জের শুরুর ইটারেটর।
• last: রেঞ্জের শেষের ইটারেটর।
• pred: একটি বাইনারি প্রেডিকেট (ঐচ্ছিক), যা দুটি উপাদানের মধ্যে তুলনা করে।

উদাহরণগুলো বাংলায় ব্যাখ্যা

উদাহরণ ১: ডিফল্ট adjacent_find()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 3, 4, 5};
    auto it = adjacent_find(v.begin(), v.end());
    if (it != v.end()) {
        cout << "পাশাপাশি একই উপাদান পাওয়া গেছে: " << *it << endl;
    } else {
        cout << "কোনো পাশাপাশি একই উপাদান নেই" << endl;
    }
    return 0;
}

আউটপুট: পাশাপাশি একই উপাদান পাওয়া গেছে: ২

ব্যাখ্যা: এখানে ভেক্টরে {1, 2, 2, 3, 4, 5} আছে। adjacent_find() দেখেছে যে ২ এবং ২ পাশাপাশি আছে। তাই প্রথম ২-এর ইটারেটর রিটার্ন করেছে।

উদাহরণ ২: কোনো পাশাপাশি একই উপাদান না থাকলে

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7};
    auto it = adjacent_find(v.begin(), v.end());
    if (it != v.end()) {
        cout << "পাশাপাশি একই উপাদান পাওয়া গেছে: " << *it << endl;
    } else {
        cout << "কোনো পাশাপাশি একই উপাদান নেই" << endl;
    }
    return 0;
}

আউটপুট: কোনো পাশাপাশি একই উপাদান নেই

ব্যাখ্যা: এখানে {1, 3, 5, 7}-এ কোনো পাশাপাশি একই সংখ্যা নেই। তাই v.end() রিটার্ন করেছে।

উদাহরণ ৩: কাস্টম প্রেডিকেট ব্যবহার

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sumEqualToTen(int a, int b) {
    return (a + b == 10);
}

int main() {
    vector<int> v = {3, 7, 4, 6, 5};
    auto it = adjacent_find(v.begin(), v.end(), sumEqualToTen);
    if (it != v.end()) {
        cout << "পাশাপাশি উপাদান যার সমষ্টি ১০: " << *it << " এবং " << *(it + 1) << endl;
    } else {
        cout << "এমন কোনো জোড়া নেই" << endl;
    }
    return 0;
}

আউটপুট: পাশাপাশি উপাদান যার সমষ্টি ১০: ৩ এবং ৭

ব্যাখ্যা: এখানে {3, 7, 4, 6, 5}-এ ৩ এবং ৭-এর সমষ্টি ১০। তাই প্রথম উপাদান ৩-এর ইটারেটর রিটার্ন করেছে।

এই টিউটোরিয়ালটি তৈরি করেছেন Shakil Babu। আরও প্রোগ্রামিং টিউটোরিয়ালের জন্য আমাদের সাথে থাকুন!

Read More

Frequency Counter Algorithm: for String and Array Problem

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম: বাংলায় বিস্তারিত গাইড

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম কী?

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

কেন ফ্রিকোয়েন্সি কাউন্টার ব্যবহার করা হয়?

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

কখন এটি ব্যবহার করবেন?

যখন আপনার কাছে একটি ডেটা সেট থাকবে এবং আপনি জানতে চাইবেন প্রতিটি উপাদান কতবার পুনরাবৃত্তি হয়েছে, তখন এই অ্যালগরিদমটি ব্যবহার করা হয়। উদাহরণস্বরূপ:

• একটি স্ট্রিংয়ে প্রতিটি অক্ষরের সংখ্যা গণনা।
• একটি অ্যারেতে ডুপ্লিকেট উপাদান খুঁজে বের করা।
• দুটি ডেটা সেটের তুলনা করা।

বিস্তারিত ব্যাখ্যা: শুরু থেকে অ্যাডভান্সড লেভেল

এই অ্যালগরিদমটি ধাপে ধাপে বোঝার জন্য আমরা পাইথনে কোডের মাধ্যমে ৫টি উদাহরণ দেখব।

ধাপ ১: মৌলিক ধারণা

এই অ্যালগরিদমে আমরা একটি ডিকশনারি (হ্যাশ ম্যাপ) ব্যবহার করি। প্রতিটি উপাদানকে কী এবং এর ফ্রিকোয়েন্সিকে মান হিসেবে সংরক্ষণ করা হয়।

উদাহরণ ১: স্ট্রিংয়ে অক্ষর গণনা

                
def count_frequency(string):
    freq = {}
    for char in string:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
    return freq

text = "বাংলা"
result = count_frequency(text)
print(result)
                
            

আউটপুট: {'ব': 1, 'া': 2, 'ং': 1, 'ল': 1}

ব্যাখ্যা: "বাংলা" স্ট্রিংয়ে "া" দুইবার এসেছে, বাকি অক্ষর একবার করে।

উদাহরণ ২: লিস্টে সংখ্যা গণনা

                
def count_numbers(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

numbers = [1, 2, 3, 2, 1, 4]
result = count_numbers(numbers)
print(result)
                
            

আউটপুট: {1: 2, 2: 2, 3: 1, 4: 1}

ব্যাখ্যা: ১ এবং ২ দুইবার করে এসেছে, ৩ এবং ৪ একবার করে।

ধাপ ২: মাঝারি জটিলতার সমস্যা

উদাহরণ ৩: দুটি স্ট্রিং একই কিনা চেক করা

                
def same_frequency(str1, str2):
    if len(str1) != len(str2):
        return False
    freq1 = count_frequency(str1)
    freq2 = count_frequency(str2)
    return freq1 == freq2

print(same_frequency("abba", "baba"))  # True
print(same_frequency("abc", "def"))    # False
                
            

ব্যাখ্যা: "abba" এবং "baba" তে a=2, b=2 আছে, তাই True। "abc" এবং "def" ভিন্ন।

ধাপ ৩: অ্যাডভান্সড ব্যবহার

উদাহরণ ৪: ডুপ্লিকেট সংখ্যা খুঁজে বের করা

                
def find_duplicates(arr):
    freq = count_numbers(arr)
    duplicates = [key for key, value in freq.items() if value > 1]
    return duplicates

numbers = [1, 2, 3, 2, 4, 1, 5]
result = find_duplicates(numbers)
print(result)
                
            

আউটপুট: [1, 2]

ব্যাখ্যা: ১ এবং ২ দুইবার করে এসেছে, তাই ডুপ্লিকেট।

উদাহরণ ৫: সর্বাধিক ফ্রিকোয়েন্সি খুঁজে বের করা

                
def max_frequency(arr):
    freq = count_numbers(arr)
    max_item = max(freq, key=freq.get)
    return max_item, freq[max_item]

numbers = [1, 2, 2, 3, 2, 4]
item, count = max_frequency(numbers)
print(f"সর্বাধিক ফ্রিকোয়েন্সি: {item}, সংখ্যা: {count}")
                
            

আউটপুট: সর্বাধিক ফ্রিকোয়েন্সি: 2, সংখ্যা: 3

ব্যাখ্যা: ২ তিনবার এসেছে, যা সর্বাধিক।

উপসংহার

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম একটি শক্তিশালী এবং দক্ষ টুল যা সহজ থেকে জটিল সমস্যা সমাধানে ব্যবহৃত হয়। এটি O(n) সময় জটিলতায় কাজ করে এবং হ্যাশ ম্যাপের সাহায্যে দ্রুত ফলাফল দেয়। এই গাইড এবং উদাহরণগুলো আপনার কোডিং দক্ষতা বাড়াতে সাহায্য করবে।

তারিখ: ২৭ মার্চ, ২০২৫

Read More

Codeforces problem(800) :- Beautiful matrix

Beautiful Matrix সমস্যার সি++ সমাধান - বাংলা ব্যাখ্যা

এই পোস্টে আমরা "Beautiful Matrix" নামের একটি প্রোগ্রামিং সমস্যার সমাধান করবো সি++ ভাষায়। সমস্যাটির উদ্দেশ্য হলো একটি ৫×৫ ম্যাট্রিক্সে একটি "১" কে মাঝখানে (৩য় সারি, ৩য় কলাম) নিয়ে আসার জন্য সর্বনিম্ন কতগুলো মুভ লাগবে তা বের করা। প্রতিটি মুভে আমরা পাশাপাশি দুটি সারি বা কলাম অদলবদল করতে পারি। এখানে আমি আমার সমাধানের প্রতিটি লাইন বাংলায় বিস্তারিতভাবে ব্যাখ্যা করবো।

সমস্যার বিবরণ

আমাদের দেওয়া আছে একটি ৫×৫ ম্যাট্রিক্স যেখানে ২৪টি শূন্য (০) এবং একটি এক (১) আছে। আমাদের লক্ষ্য হলো এই "১" কে ম্যাট্রিক্সের মাঝখানে (৩য় সারি, ৩য় কলাম, বা ০-ভিত্তিক ইনডেক্সে ২,২) নিয়ে আসা। আমরা শুধু পাশের সারি বা কলাম অদলবদল করতে পারি।

সি++ কোড

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int n = 5;
    vector<vector<int>> matrix(n, vector<int>(n));
    int row, col;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if(matrix[i][j] == 1) {
                row = i;
                col = j;
            }
        }
    }
    int moves = abs(row - 2) + abs(col - 2);
    cout << moves << endl;
    return 0;
}

লাইন বাই লাইন বাংলা ব্যাখ্যা

লাইন ১: #include <bits/stdc++.h>

এই লাইনটি সি++ এর স্ট্যান্ডার্ড লাইব্রেরির সব হেডার ফাইল ইনক্লুড করে। এটি আমাদের প্রয়োজনীয় সব ফাংশন যেমন vector, cin, cout, abs ইত্যাদি ব্যবহার করতে দেয়। এটি একটি শর্টকাট যা সাধারণত প্রতিযোগিতামূলক প্রোগ্রামিংয়ে ব্যবহৃত হয়।

লাইন ২: using namespace std;

এটি আমাদের std নেমস্পেসের সবকিছু সরাসরি ব্যবহার করার অনুমতি দেয়। যেমন, আমাদের std::cin এর পরিবর্তে শুধু cin লিখতে হবে।

লাইন ৪: int main() {

এটি প্রোগ্রামের মূল ফাংশন। প্রোগ্রাম শুরু হয় এখান থেকে এবং এটি একটি ইন্টিজার (পূর্ণসংখ্যা) রিটার্ন করে।

লাইন ৫: const int n = 5;

এখানে আমরা একটি ধ্রুবক (constant) ভেরিয়েবল n ডিফাইন করছি যার মান ৫। এটি ম্যাট্রিক্সের আকার নির্দেশ করে (৫×৫)। const মানে এটি পরিবর্তন করা যাবে না।

লাইন ৬: vector<vector<int>> matrix(n, vector<int>(n));

এটি একটি ৫×৫ ম্যাট্রিক্স তৈরি করে vector ব্যবহার করে। vector হলো একটি গতিশীল অ্যারে। এখানে:

• vector<int>(n) মানে ৫টি ইন্টিজারের একটি ভেক্টর (ডিফল্ট মান ০)।
• vector<vector<int>> matrix(n, ...) মানে ৫টি সারির একটি ভেক্টর, যেখানে প্রতিটি সারিতে ৫টি কলাম আছে।

ফলে আমরা একটি ৫×৫ ম্যাট্রিক্স পাই।

লাইন ৭: int row, col;

এখানে দুটি ভেরিয়েবল row এবং col ডিফাইন করা হয়েছে। এগুলো "১" এর বর্তমান সারি এবং কলামের ইনডেক্স সংরক্ষণ করবে।

লাইন ৮: for(int i = 0; i < n; i++) {

এটি একটি লুপ যা ০ থেকে ৪ পর্যন্ত চলে (মোট ৫ বার, কারণ n = 5)। এটি ম্যাট্রিক্সের প্রতিটি সারির জন্য কাজ করে। i হলো সারির ইনডেক্স।

লাইন ৯: for(int j = 0; j < n; j++) {

এটি একটি ভেতরের লুপ যা প্রতিটি সারির ৫টি কলামের জন্য চলে। j হলো কলামের ইনডেক্স।

লাইন ১০: cin >> matrix[i][j];

এটি ব্যবহারকারীর কাছ থেকে ইনপুট নেয় এবং matrix[i][j] পজিশনে সংরক্ষণ করে। আমরা ৫টি লাইনে ৫টি করে সংখ্যা ইনপুট দেবো।

লাইন ১১: if(matrix[i][j] == 1) {

এটি চেক করে যে বর্তমান পজিশনে (i, j) যদি "১" থাকে।

লাইন ১২: row = i;

যদি "১" পাওয়া যায়, তাহলে row ভেরিয়েবলে সেই সারির ইনডেক্স (i) সেট করা হয়।

লাইন ১৩: col = j;

একইভাবে, col ভেরিয়েবলে "১" এর কলামের ইনডেক্স (j) সেট করা হয়।

লাইন ১৪-১৫: } এবং }

এগুলো দুটি for লুপ বন্ধ করে। ইনপুট শেষে আমরা "১" এর পজিশন জানি।

লাইন ১৬: int moves = abs(row - 2) + abs(col - 2);

এটি সর্বনিম্ন মুভের সংখ্যা গণনা করে:

• abs(row - 2): "১" এর বর্তমান সারি থেকে টার্গেট সারি (২) এর দূরত্ব। abs পরম মান দেয়।
• abs(col - 2): "১" এর বর্তমান কলাম থেকে টার্গেট কলাম (২) এর দূরত্ব।
• দুটির যোগফল হলো মোট মুভ।

এটি ম্যানহাটন দূরত্ব নামে পরিচিত।

লাইন ১৭: cout << moves << endl;

এটি moves এর মান প্রিন্ট করে এবং একটি নতুন লাইন যোগ করে।

লাইন ১৮: return 0;

এটি প্রোগ্রাম শেষ করে এবং ০ রিটার্ন করে, যা বোঝায় প্রোগ্রাম সফলভাবে চলেছে।

লাইন ১৯: }

এটি main ফাংশন বন্ধ করে।

উদাহরণ

ইনপুট:

0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

ব্যাখ্যা: "১" আছে (১, ৪) পজিশনে। মুভ = |১-২| + |৪-২| = ১ + ২ = ৩।

আউটপুট: ৩

কেন এটি কাজ করে?

প্রতিটি মুভে "১" একটি পজিশন সরে। সারি এবং কলামের দূরত্ব আলাদাভাবে গণনা করে আমরা সর্বনিম্ন মুভ পাই। এটি সবচেয়ে দ্রুত এবং সহজ পদ্ধতি।

Problem link: https://codeforces.com/contest/263/problem/A

Read More

Sliding window algorithm in bangla : easy for all

স্লাইডিং উইন্ডো অ্যালগরিদম: বাংলায় বিস্তারিত গাইড

স্বাগতম! এই ব্লগে আমরা আলোচনা করবো স্লাইডিং উইন্ডো অ্যালগরিদম সম্পর্কে, যা প্রোগ্রামিং এবং অ্যালগরিদম সমাধানে একটি অত্যন্ত কার্যকরী টেকনিক। এটি কী, কীভাবে কাজ করে, কোথায় ব্যবহৃত হয়, এবং পাইথন ও সি++ এর একাধিক উদাহরণ সহ বিস্তারিতভাবে বাংলায় ব্যাখ্যা করা হবে।

স্লাইডিং উইন্ডো অ্যালগরিদম কী?

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

এটি কীভাবে কাজ করে?

স্লাইডিং উইন্ডো টেকনিক প্রধানত দুই ধরনের হয়:

• নির্দিষ্ট আকারের উইন্ডো (Fixed Size Window): উইন্ডোর আকার স্থির থাকে।
• পরিবর্তনশীল আকারের উইন্ডো (Variable Size Window): উইন্ডোর আকার প্রয়োজন অনুযায়ী পরিবর্তিত হয়।

এটি ডেটার একটি অংশ প্রক্রিয়া করে এবং তারপর উইন্ডোটি সামনে সরিয়ে পরবর্তী অংশে যায়।

কোথায় ব্যবহৃত হয়?

স্লাইডিং উইন্ডো বিভিন্ন প্রোগ্রামিং সমস্যায় ব্যবহৃত হয়, যেমন:

• সর্বাধিক বা সর্বনিম্ন উপ-অ্যারে খুঁজে বের করা।
• নির্দিষ্ট যোগফলের উপ-অ্যারে খুঁজে পাওয়া।
• স্ট্রিং-এ প্যাটার্ন ম্যাচিং।
• ডেটা স্ট্রিম প্রক্রিয়াকরণ।

উদাহরণ ১: নির্দিষ্ট আকারের উইন্ডো (সর্বাধিক যোগফল)

ধরা যাক, আমাদের অ্যারে [1, -3, 2, 1, -1, 4] এবং আমরা ৩টি উপাদানের সর্বাধিক যোগফল চাই।

পাইথন কোড

arr = [1, -3, 2, 1, -1, 4]
k = 3  # উইন্ডোর আকার
max_sum = float('-inf')

for i in range(len(arr) - k + 1):
    window_sum = sum(arr[i:i + k])
    max_sum = max(max_sum, window_sum)
    print(f"উইন্ডো {i+1}: {arr[i:i + k]}, যোগফল: {window_sum}")

print(f"সর্বাধিক যোগফল: {max_sum}")
        

সি++ কোড

#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -3, 2, 1, -1, 4};
    int k = 3;
    int max_sum = INT_MIN;

    for (int i = 0; i <= arr.size() - k; i++) {
        int window_sum = 0;
        for (int j = i; j < i + k; j++) {
            window_sum += arr[j];
        }
        max_sum = max(max_sum, window_sum);
        cout << "উইন্ডো " << i + 1 << ": ";
        for (int j = i; j < i + k; j++) cout << arr[j] << " ";
        cout << ", যোগফল: " << window_sum << endl;
    }
    cout << "সর্বাধিক যোগফল: " << max_sum << endl;
    return 0;
}
        

আউটপুট:

উইন্ডো 1: [1, -3, 2], যোগফল: 0
উইন্ডো 2: [-3, 2, 1], যোগফল: 0
উইন্ডো 3: [2, 1, -1], যোগফল: 2
উইন্ডো 4: [1, -1, 4], যোগফল: 4
সর্বাধিক যোগফল: 4
        

উদাহরণ ২: পরিবর্তনশীল আকারের উইন্ডো (নির্দিষ্ট যোগফল)

ধরা যাক, অ্যারে [1, -1, 2, 3, -2, 4] এবং আমরা যোগফল ৫ চাই।

পাইথন কোড

arr = [1, -1, 2, 3, -2, 4]
target = 5
curr_sum = 0
start = 0

for end in range(len(arr)):
    curr_sum += arr[end]
    while curr_sum > target and start <= end:
        curr_sum -= arr[start]
        start += 1
    if curr_sum == target:
        print(f"উপ-অ্যারে: {arr[start:end+1]}, যোগফল: {curr_sum}")
        

সি++ কোড

#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -1, 2, 3, -2, 4};
    int target = 5;
    int curr_sum = 0, start = 0;

    for (int end = 0; end < arr.size(); end++) {
        curr_sum += arr[end];
        while (curr_sum > target && start <= end) {
            curr_sum -= arr[start];
            start++;
        }
        if (curr_sum == target) {
            cout << "উপ-অ্যারে: [";
            for (int i = start; i <= end; i++) {
                cout << arr[i] << (i < end ? ", " : "");
            }
            cout << "], যোগফল: " << curr_sum << endl;
        }
    }
    return 0;
}
        

আউটপুট:

উপ-অ্যারে: [2, 3], যোগফল: 5
        

উদাহরণ ৩: স্ট্রিং-এ স্লাইডিং উইন্ডো (দীর্ঘতম সাবস্ট্রিং)

ধরা যাক, স্ট্রিং "abcabcbb" এবং আমরা দীর্ঘতম সাবস্ট্রিং চাই যেখানে কোনো অক্ষর পুনরাবৃত্তি নেই।

পাইথন কোড

s = "abcabcbb"
char_map = {}
start = 0
max_length = 0
max_substring = ""

for end in range(len(s)):
    if s[end] in char_map and char_map[s[end]] >= start:
        start = char_map[s[end]] + 1
    else:
        if end - start + 1 > max_length:
            max_length = end - start + 1
            max_substring = s[start:end + 1]
    char_map[s[end]] = end

print(f"দীর্ঘতম সাবস্ট্রিং: {max_substring}, দৈর্ঘ্য: {max_length}")
        

সি++ কোড

#include 
#include 
#include 
using namespace std;

int main() {
    string s = "abcabcbb";
    unordered_map char_map;
    int start = 0, max_length = 0;
    string max_substring;

    for (int end = 0; end < s.length(); end++) {
        if (char_map.find(s[end]) != char_map.end() && char_map[s[end]] >= start) {
            start = char_map[s[end]] + 1;
        } else if (end - start + 1 > max_length) {
            max_length = end - start + 1;
            max_substring = s.substr(start, max_length);
        }
        char_map[s[end]] = end;
    }

    cout << "দীর্ঘতম সাবস্ট্রিং: " << max_substring << ", দৈর্ঘ্য: " << max_length << endl;
    return 0;
}
        

আউটপুট:

দীর্ঘতম সাবস্ট্রিং: abc, দৈর্ঘ্য: 3
        

সুবিধা ও অসুবিধা

সুবিধা:

• সময় জটিলতা কমায় (O(n²) থেকে O(n))।
• বাস্তবায়ন সহজ এবং বোঝা যায়।
• অ্যারে ও স্ট্রিং উভয় ক্ষেত্রেই কার্যকর।

অসুবিধা:

• সব সমস্যার জন্য উপযুক্ত নয়।
• কিছু ক্ষেত্রে অতিরিক্ত মেমোরি লাগতে পারে।

উপসংহার

স্লাইডিং উইন্ডো অ্যালগরিদম প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি শক্তিশালী এবং জনপ্রিয় টেকনিক। এই ব্লগে আমরা এটির বিস্তারিত ব্যাখ্যা, পাইথন ও সি++ এর উদাহরণ, এবং এর প্রয়োগ দেখেছি। এটি শিখে আপনি অনেক জটিল সমস্যা সহজে সমাধান করতে পারবেন।

স্লাইডিং উইন্ডো প্র্যাকটিস প্রবলেম

এখানে কিছু জনপ্রিয় প্রোগ্রামিং প্ল্যাটফর্ম থেকে স্লাইডিং উইন্ডো সম্পর্কিত সমস্যার লিঙ্ক দেওয়া হলো। এগুলো অনুশীলন করে আপনি আপনার দক্ষতা বাড়াতে পারেন।

• CodeChef: Maximum Subarray Sum with K Elements
• CodeChef: Chef and Subarray
• Codeforces: Longest k-Good Segment
• Codeforces: Subarray Counting
• LeetCode: Maximum Average Subarray I
• LeetCode: Longest Substring Without Repeating Characters
• LeetCode: Sliding Window Maximum
• LeetCode: Minimum Size Subarray Sum

Read More

>প্রিফিক্স সাম: সম্পূর্ণ ব্যাখ্যা বাংলায়!

 

প্রিফিক্স সাম কি?

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

প্রিফিক্স সাম কেন ব্যবহার করা হয়?

ধরি, আপনার কাছে একটি অ্যারে রয়েছে: [1, 2, 3, 4, 5]. এখন আপনি চাইতেছেন, arr[l] থেকে arr[r] পর্যন্ত যোগফল বের করতে। আপনি চাইলে অন্যভাবে খুব সহজেই করতে পারবেন কিন্তু অনলাইন জাজে Time Limit Exceed(TLE) খেতে পারেন। আর এই সমস্যা খুব সহজেই আপনি প্রিফিক্স সামের সাহায্যে সমাধান করতে পারবেন।

প্রিফিক্স সাম ব্যবহার না করলে আপনাকে প্রতি বার লুপ চালাতে হয়। কিন্তু যদি প্রিফিক্স সাম ব্যবহার করেন তাহলে একবার হিসাব করে, পরবর্তী সময়গুলোতে আপনি মাত্র O(1) সময়ে কাজটি করতে পারবেন।

প্রিফিক্স সামের সুবিধা :

প্রিফিক্স সামের সুবিধা হল যে এটি একবার অ্যারের উপাদানগুলোর যোগফল হিসাব করে সংরক্ষণ করে। যার পরবর্তী সময়ে সাবঅ্যারের যোগফল বের করার জন্য আমাদের সময় O(1) থাকে।

যেমনঃ, প্রিফিক্স সাম তৈরি করতে সময় লাগবে O(n), এবং সাবঅ্যারের যোগফল বের করতে O(1) সময় লাগে।

প্রিফিক্স সাম গণনার উদাহরণ :

C++ উদাহরণ

#include
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    int prefix[n];
    prefix[0] = arr[0]; // প্রথম উপাদান কপি করছি
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i]; // প্রতিটি উপাদান যোগ করতে থাকছি
    }
    cout << "Prefix Sum Array: ";
    for (int i = 0; i < n; i++) {
        cout << prefix[i] << " "; // আউটপুট: 1 3 6 10 15
    }
    return 0;
}
        

Python উদাহরণ

def prefix_sum(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]  # প্রথম উপাদান কপি করছি
    for i in range(1, len(arr)):
        prefix[i] = prefix[i - 1] + arr[i]  # প্রতিটি উপাদান যোগ করতে থাকছি
    return prefix

arr = [1, 2, 3, 4, 5]
print("Prefix Sum Array:", prefix_sum(arr))  # আউটপুট: [1, 3, 6, 10, 15]
        

কিভাবে সাবঅ্যারের যোগফল বের করা যাবে?

যদি আপনি জানেন যে আপনার প্রিফিক্স সাম অ্যারে তৈরি হয়ে গেছে, তাহলে আপনার সাবঅ্যারের যোগফল O(1) সময়ে বের করা যাবে। এই কোডটি দেখুন:

C++ উদাহরণ

int rangeSum(int prefix[], int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];  // সাবঅ্যারের যোগফল বের করা
}
        

Python উদাহরণ

def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l - 1]  # সাবঅ্যারের যোগফল বের করা
        

প্রিফিক্স সামের সুবিধা ও প্রয়োগ

প্রিফিক্স সামের সবচেয়ে বড় সুবিধা হলো, আপনি একবার যোগফল হিসাব করে সংরক্ষণ করে ফেললে, পরবর্তীতে সাবঅ্যারের যোগফল বের করতে মাত্র O(1) সময়ে কাজ করতে পারবেন। এতে আপনার প্রোগ্রাম আরও দ্রুত কাজ করবে।

প্রিফিক্স সাম ব্যবহার করে আপনি বিভিন্ন ধরনের সমস্যা যেমন, সাবঅ্যারের যোগফল, সাবঅ্যারের গড় বের করা, এবং অন্যান্য সংখ্যাসূচক সমস্যা সমাধান করতে পারবেন।

প্র্যাকটিস প্রবলেম

• Codeforces 1650B
• CodeChef SUBARRAYSUM
• Codeforces 1676D

Read More

JavaScript ES6: Understanding Default Parameters

🎯 What Are Default Parameters in JavaScript?

Imagine going to a coffee shop, and the barista automatically gives you a cappuccino because you didn't specify your order. That’s what JavaScript ES6 Default Parameters do! 🎉

📌 Before ES6: The Struggle Was Real

Before ES6, we had to manually check if a function parameter was provided. If not, we assigned a default value like this:

const greet = (name) => {
    name = name || 'Stranger';
    console.log(`Hello, ${name}!`);
}

greet('Alice'); // Output: Hello, Alice!
greet(); // Output: Hello, Stranger!
        

This was okay but not elegant. JavaScript developers wanted a cleaner solution. And then came ES6... 🚀

✅ ES6 Default Parameters: The Smart Way

With ES6, we can directly assign default values in the function parameters. Check this out:

const greet = (name = 'Stranger') => {
    console.log(`Hello, ${name}!`);
}

greet('Alice'); // Output: Hello, Alice!
greet(); // Output: Hello, Stranger!
        

Much cleaner, right? No more `name = name || 'Stranger'` nonsense! 😎

🤔 Why Use Default Parameters?

• 💡 Prevents `undefined` values
• 🚀 Simplifies code
• ⏳ Saves time (because we devs are lazy 😂)
• 🎯 Improves code readability

🛠 More Fun with Default Parameters

Example 1: Calculating Discounted Price

const calculatePrice = (price, discount = 0.10) => {
    return price - (price * discount);
}

console.log(calculatePrice(100)); // Output: 90
console.log(calculatePrice(100, 0.20)); // Output: 80
        

Example 2: Multiplication Table

const multiplicationTable = (num = 1) => {
    for(let i = 1; i <= 10; i++) {
        console.log(`${num} x ${i} = ${num * i}`);
    }
}

multiplicationTable(5); // Outputs table of 5
multiplicationTable(); // Outputs table of 1
        

🚀 Advanced Use Cases

Default Parameters with Objects

const userInfo = (user = { name: 'Guest', age: 18 }) => {
    console.log(`User: ${user.name}, Age: ${user.age}`);
}

userInfo({ name: 'Alice', age: 25 });
userInfo();
        

Using Functions as Default Parameters

const randomNumber = () => Math.floor(Math.random() * 100);

const showNumber = (num = randomNumber()) => {
    console.log(`Generated number: ${num}`);
}

showNumber(); // Outputs a random number
showNumber(42); // Outputs 42
        

🎉 Final Thoughts

Default Parameters in ES6 are a game-changer! They make your code cleaner, smarter, and easier to read. Now, go and use them in your projects! 🚀

🔗 Share This Article

Share on Twitter

Read More

ডিফল্ট(Default) প্যারামিটার ইন জাভাস্ক্রিপ্ট ইএস৬(ES6)

 

জাভাস্ক্রিপ্ট ইএস ৬(ES6) এ আরেকটা চমৎকার কনসেপ্ট হলো ডিফল্ট(Default) প্যারামিটার যা ফাংশনে ব্যাবহার করা হয় । কোনো ফাংশন ডিফাইন করার সময় এর সাথে দেওয়া প্যারামিটারের একটা ডিফল্ট ভ্যালু সেট করে দেওয়াটাই হইলো ডিফল্ট(Default) প্যারামিটার ।

যদিও জাভাস্ক্রিপ্ট ইএস৫ এ এই কনসেপ্ট ছিলো নাহ তারপরেও লজিক ব্যাবহার করে ডিফল্ট প্যারামিটারের কাজটা সেরে ফেলা যেত। আমরা এখন ইএস৫ এবং ইএস৬ দুইটাতেই দেখবো যে - ডিফল্ট প্যারামিটার কনসেপ্ট আসার আগে কেমনে হ্যান্ডেল করা হতো আর আসার পর কেমনে করা হয় ।

const info = (Name, Town) => {
    // do something
}
info();

ধরুন, আমাদের info নামে একটা ফাংশন আছে, যার দুইটা প্যারামিটার আছে Name এবং Town নামে । যদি কেউ ফাংশন কল করার পর প্যারামিটার এর ভ্যালু পাস করে তাহলে সেই অনুযায়ী রেজাল্ট দিবে আর যদি ভ্যালু পাস নাহ করা হয় তাহলে ডিফল্টভাবে Name='Shakil Babu' এবং Town='Bogura' ধরে রেজাল্ট দিবে।

প্রথমে চলুন আমরা এইটা ইএস৫ এ কেমনে হ্যান্ডেল করে সেইটা দেখি -

const info = (Name, Town) => {

    Name ? Name = Name : Name = 'Shakil Babu' ; 
    Town ? Town = Town : Town = 'Bogura' 
    console.log(`I am ${Name} from ${Town}`);
    
}

এখন কেউ যদি, ফাংশন কল করে প্যারামিটারের ভ্যালু পাস করে তাহলে সেই অনুযায়ী আমাদের আউটপুট দেখাবে :-

info('Torikus', 'Dinajpur');
// output :
// I am Torikus from Dinajpur

এবার যদি, প্যারামিটারের ভ্যালু পাস নাহ করা হয় :-

info();
// output :
// I am Shakil Babu from Bogura

দেখছেন ? আমাদের ডিফল্টভাবে সেট করে দেওয়া ভ্যালুগুলো নিয়েই কাজ করেছে।

এখন এই সেইম কাজটা ইএস৬ এর ডিফল্ট(Default) প্যারামিটার দিয়ে করা যাক -

const info = (Name='Shakil Babu', Town='Bogura') => {
    console.log(`I am ${Name} from ${Town}`);
}

যদি কেউ প্যারামিটারের ভ্যালু পাস করে :-

info('Torikus', 'Dinajpur');
// output :
// I am Torikus from Dinajpur

এবার যদি, প্যারামিটারের ভ্যালু পাস নাহ করা হয় -

info();
// output :
// I am Shakil Babu from Bogura

আমরা কিন্তু সেইম কাজটা অনেক সহজ ওয়েতে ইএস৬ এর ডিফল্ট(Default) প্যারামিটার দিয়ে করলাম । আর এইটাই স্ট্যান্ডার্ড ওয়ে যা আগে ডেভেলপাররা চাইতো এবং ফাইনালি ইএস৬ সেইটা এনে দিয়েছে ।

আশা করি আপনারা ডিফল্ট(Default) প্যারামিটার কনসেপ্ট বুঝতে পারছেন ।

এবার ছোট্ট একটা প্রব্লেমের সাথে ডিফল্ট(Default) প্যারামিটার ব্যাবহার করা যাক :-

প্রব্লেম - একটি নামতা প্রিন্ট করার প্রোগ্রাম লিখতে হবে যেখানে ফাংশন প্যারামিটার হিসেবে একটি নাম্বার নিবে । যদি প্যারামিটারের ভ্যালু পাস করা হয় তাহলে সেই ভ্যালু অনুযায়ী নয়তো ১ এর ঘরের নামতা প্রিন্ট করতে হবে ।

আপনারা কিন্তু, ইতিমধ্যে বুঝে ফেলছেন এইটা কিভাবে করতে হবে । এখানে অবশ্যই ডিফল্ট(Default) প্যারামিটারের ব্যাবহার করতে হবে। তো চলুন দেখা যাক -

const multipicationTable = (number = 1) =>{
    for (let i = 1; i <= 10 ;  i++) {
        console.log(`${number}*${i} = ${i*number}`);
    }
}

এখন, উপরোক্ত ফাংশন কল করে আমরা একটা নাম্বার ভ্যালু পাস করি যেমন - 10 ।

multipicationTable(10);

আউটপুট হবে :-

10*1 = 10
10*2 = 20
10*3 = 30
10*4 = 40
10*5 = 50
10*6 = 60
10*7 = 70
10*8 = 80
10*9 = 90
10*10 = 100

যদি, প্যারামিটারের কোনো ভ্যালু পাস নাহ করা হয় :-

multipicationTable();

তখন আউটপুট হবে :-

1*1 = 1
1*2 = 2
1*3 = 3
1*4 = 4
1*5 = 5
1*6 = 6
1*7 = 7
1*8 = 8
1*9 = 9
1*10 = 10

আমাদের প্রব্লেমের সমাধান পেয়ে গেছি । আশা করি, ডিফল্ট(Default) প্যারামিটার নিয়ে আপনাদের আর কোনো অসুবিধা হবে নাহ ।

ধন্যবাদ সবাইকে ।

Read More

How to create a string character map in JavaScript

 

 

হে সুন্দর মানুষজন,

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

স্ট্রিং কাকে বলে ?

আমরা তো সবাই জানি যে স্ট্রিং কি বা কাকে বলে । একদম সহজ ভাবে বলতে গেলে জাভাস্ক্রিপ্টে সিঙ্গেল বা ডাবল কোটেশানের মাঝে যাই থাকে তাকেই স্ট্রিং বলে । স্ট্রিং মুলত কতগুলো ক্যারেক্টারের সমষ্টি ।

ক্যারেক্টার ম্যাপ কী ?

কোনো একটা স্ট্রিং এ কি কি ক্যারেক্টার আছে তার লিস্ট করা সাথে কোন ক্যারেক্টার কতোবার আছে তার হিসেব করা । যেমন ধরি, আমাদের কাছে "babu" নামে একটি স্ট্রিং আছে, তাহলে এর ক্যারেক্টার ম্যাপ হবে এইরকম :-

{
    b: 2,
    a: 1,
    u: 1
}

আমরা দেখতে পাইতেছি যে, "babu" নামের এই স্ট্রিং টাতে কিন্তু b ক্যারেক্টার দুইটি তাই b : 2 এমনভাবে দেখাচ্ছে এবং a,u একটি করে তাই তাদের পরিমাণটাও একটি(1) করে দেখাচ্ছে।

ক্যারেক্টার ম্যাপ তৈরি করার সুবিধা কী ?

কোনো একটি স্ট্রিং এর ক্যারেক্টার ম্যাপ তৈরি করে খুব সহজেই বিভিন্ন স্ট্রিং রিলেটেড সমস্যা সমাধান করতে পারবেন যেমন -

১। স্ট্রিং এ সবচেয়ে কমন ক্যারেক্টার কোনটি বা কোনগুলো ?

২। স্ট্রিং টি অ্যানাগ্রাম কি নাহ ?

৩। স্ট্রিং এ কোনো রিপিটেড ক্যারেক্টার আছে কি নাহ ?

- ক্যারেক্টার ম্যাপ তৈরি -

const characterMap = (str) => {
  const charMap = {};
  str.split("").forEach((char) => {
    if (charMap[char]) {
      charMap[char]++;
    } else {
      charMap[char] = 1;
    }
  });

  return charMap;
};

আমাদের ক্যারেক্টার ম্যাপ তৈরি, এখন চেক করে দেখা যাক যে ঠিক-ঠাক উত্তর দিচ্ছে কি নাহ ?

const charMap = characterMap("babu");
console.log(charMap)

OUTPUT :

{
    b: 2,
    a: 1,
    u: 1
}

সবকিছু ঠিক-ঠাক । তবে একটা কথা বলে রাখা ভালো যে আপনি অনেক ভাবেই ক্যারেক্টার ম্যাপ তৈরি করতে পারেন । আপনাকে যে উপরোক্ত ভাবেই ক্যারেক্টার ম্যাপ তৈরি করতে হবে সেই রকম কোনো বাধা-ধরা নিয়ম নেই ।

- Another way to create CharacterMap -

const characterMap = (str) => {
  const charMap = {};
  for (let char of str) {
    charMap[char] ? charMap[char]++ : (charMap[char] = 1);
  }

  return charMap;
};

- Check it -

const charMap = characterMap("hello");
console.log(charMap)

OUTPUT :

{
    h: 1,
    e: 1,
    l: 2,
    o:1
}

আশা করি বুঝতে পারছেন। ধন্যবাদ সবাইকে ।

Read More

for of loop in javascript - ফর অব লুপ

 

জাভাস্ক্রিপ্ট ইএস৬(ES6) এ নতুন একটি লুপের সাথে পরিচয় করিয়ে দেওয়া হয়েছে যার নাম for...of লুপ । এই for...of লুপের সাহায্যে খুব সহজেই অ্যারে(array), সেট(set), ম্যাপ(map), স্ট্রিং(string) ইত্যাদিকে ইটারেট করা যায় ।

জাভাস্ক্রিপ্ট for...of লুপ সিনট্যাক্স :-

for (item of iterable) {
    // body of for...of
}

এখানে,

• iterable হলো যেকোনো একটি ইটারেবল(iterable) অবজেক্ট যেমন - অ্যারে(array), সেট(set), স্ট্রিং(string) ইত্যাদি ।
• item হলো ইটারেবল(iterable) অবজেক্টের ভ্যালু ।

এখন আমরা for...of লুপের ইউসকেস দেখবো অর্থাৎ এটি কিভাবে কাজ করে -

for...of with Arrays

কোনো একটা অ্যারেকে ইটারেট করার প্রয়োজন হলে আমরা for...of ব্যাবহার করতে পারি যেমন :-

// array
const friends = ['shakil', 'torikus', 'fahim'];
// using for...of
for ( let item of friends ) {
    // display the values
    console.log(item);
}

OUTPUT :-

shakil
torikus
fahim

উপরের প্রোগ্রামে friends আরেকে ইটারেট করা হয়েছে অর্থাৎ অ্যারের ভেতর লুপ থ্রো করা হয়েছে যা অ্যারের লেন্থ পর্যন্ত চলবে । এবং item of friends এই লাইনে item নামে একটা ভ্যারিয়েবল নেওয়া হয়েছে যা friends আরের ভ্যালুকে নির্দেশ করে ।

প্রত্যেকবার লুপটি ইটারেট করার সময় কনসোলে item কে লগ করে যার ফলে উপরোক্ত আউটপুট পেয়েছি । শেষে এটি অ্যারের লেন্থ পর্যন্ত চলে ইটেরেশনকে বন্ধ করে দেয় ।

for...of with Strings :-

for...of লুপ আমরা স্ট্রিং(String) কে ইটারেট করতেও ব্যাবহার করতে পারি যেমন :-

// string
const name = 'babu';

// using for...of loop
for (let i of name) {
    console.log(i);
}

OUTPUT :-

b
a
b
u

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

for...of with Sets :-

আমরা Set এর এলিমেন্টস গুলোকে ইটারেট করতে পারি সেইম ভাবে for...of লুপ ইউস করে যেমন :-

// define Set
const set = new Set([1, 2, 3]);

// looping through Set
for (let i of set) {
    console.log(i);
}

OUTPUT :-

1
2
3

সেইম ভাবে এখানে i Set এর প্রত্যেকটা এলিমেন্ট বা ভ্যালুকে নির্দেশ করে যার প্রমাণসরূপ প্রোগ্রামের আউটপুট ।

for...of with Maps:-

আমরা সেইমভাবে Map এলিমেন্টস ইটারেট করতে পারি for...of লুপ ইউস করে যেমন :-

// define Map
let map = new Map();

// inserting elements
map.set('name', 'Jack');
map.set('age', '27');

// looping through Map
for (let [key, value] of map) {
    console.log(key + '- ' + value);
}

OUTPUT :-

name- Jack
age- 27

আশা করি বুঝতে পারছেন ।

======== শেষের কথা ========

• for...of লুপ ইউস করা হয় শুধুমাত্র ইটারেবল(iterable) অব্জেক্টসের ভ্যালুসমূহ কে ইটারেট করতে ।
• যদি কোনো ইটারেবল(iterable) অব্জেক্টসের ইনডেক্স নিয়ে কাজ করার দরকার পরে তাহলে এই লুপ ইউস না করায় ভালো ।
• for...of লুপ অবজেক্টের(object) সাথে ইউস করা যায় নাহ ।

For more information, visit MDN's documentation on for...of

Read More

ইনসার্শন সর্ট(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

বাবল সর্ট(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