পাইথনে ইন্সার্শন সর্ট এলগোরিদম ইমপ্লিমেন্ট

১৫ তারিখে ছিলো আমার স্যাটেলাইট এন্ড টেলিকমিউনিকেশন এক্সাম। তাই হাবলু দা’র সাথে সেদিন সকাল থেকে রাত ১০ পর্যন্ত কোন যোগাযোগ করা হয়নি। এক্সাম শেষে বাসায় এসে হাবলু দা’র মোবাইলে কল দিলাম। ওপাশ থেকে হাবলু দা হৃদয় ভাঙ্গা কন্ঠে বললেন কিরে মদন আজকে সারাদিন কোন যোগাযোগ করলিনা যে? আমি বললাম দাদা এক্সাম ছিলোতো তাই আজকে সারাদিন একটু দৌড়ের উপর ছিলাম।

হাবলু দা বললেন ও আচ্ছা। তা মদন এই দিকে আসবি নাকি? টঙ্গের দোকানে চা খাইতে যাইতাম! আমি আবার হাবলু দা’র কথা ফেলিনা, তাই সঙ্গে সঙ্গে বললাম ঠিক আছে ফোন রাখো আমি আসতেছি।

আমার বাসা থেকে টঙ্গের দোকায়ে যেতে প্রায় মিনিট পাঁচেক লাগে আরকি। টি-শার্ট আর থ্রি কোয়াটার প্যান্ট পরে হাটা শুরু করলাম। টঙ্গের দোকানে গিয়ে দেখি হাবলু দা মন খারাপ করে বসে আছে! আমি কিছুটা শঙ্কিত হয়ে বললাম দাদা তুমি কি আমার উপর কোন কারণে রেগে আছো? হাবলু দা বললেন নারে পাগলা তোর উপর আবার আমি রাগ করবো কেন? আর তুই কোন অন্যায় করলেও আমি সেটা হাসি মুখে তোরে শোধরানোর চেষ্টা করি! এবার আমি কিছুটা স্বস্তি বোধ করে বললাম তাহলে মন খারাপ করে আছো কেন? হাবলু দা দীর্ঘ একটা শ্বাস ফেলে বললেন ১৪ তারিখে তোর বৌদিকে মানে আমার জিএফকে বিকালে কলাবাগান মাঠে জলের গানের শো দেখতে নিয়ে যাওয়ার কথা ছিলো কিন্তু ঐ বল্টু ভাইয়ের দেওয়া বাইনারি সার্চের সমস্যার সমাধান করতে গিয়ে আমিতো ভুলেই গিয়েছিলাম। তারপর যখন মনে পরেছে তখন বাজে রাত ১০টা! সে অভিমান করে কথা বলা বন্ধ করে দিয়েছেতো তাই একটু আমার মনটা খারাপ।

এরই মাঝে চা’র খাইতে খাইতে হাবলু দা বললেন জানিস সেদিন বল্টু দা যে সর্টেড লিস্টটা দিয়েছিলোনা সেটা দেখে আমার কেমন জানি একটু জেলাস ফিল হচ্ছিলো তাই আজকে আমি সেই লিস্টটাকে ডিস-অর্ডার করে পুনরায় অর্ডার করেছি। আর এই সুযোগে একটু ইন্সার্শন সর্ট এলগোরিদমটাও ঝালাই করে নিলাম। আমি আবার এসব এলগোরিদম টেলগোরিদম বুঝি কম। হা করে শুনার পর বললাম আমারে একটু শিখাবা? বরাবরের মতোই হাবলু দা হাসিমাখা মুখে বললেন চল আমার বাসায় তোরে বুঝাই দেই এবং সেই সাথে আমিও আরেক বার ঝালাই করে নেই। যেই কথা সেই কাজ। চলে গেলাম হাবলু দা’র বাসায়।

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

তারপর তিনি বললেন আচ্ছা আমরা যে মাঝে মাঝে সবাই মিলে তাস খেলি তো সেখানে একটা বিষয় কখনো খেয়াল করে দেখেছিস? যে আমরা আমাদের ভাগে পাওয়া কার্ড গুলো একটা একটা করে নেই আর বড় থেকে ছোট বা ছোট থেকে বড় আকারে সাজাই তাইনা? আমি বললাম হ্যাঁ, তো কার্ড খেলার সাথে ইন্সার্শন সর্ট এলগোরিদমের সম্পর্ক কি? তিনি বললেন আরে বোকা সম্পর্ক আছে।  আগে ভালো করে শোন! আমি এবার চুপচাপ মনোযোগ দিয়ে শুনতে লাগলাম।

হাবলু দা এবার বললেন আমাদের ভাগের ঐ এলোমেলো কার্ড  গুলোই হচ্ছে আন-সর্টেড আইটেমস লিস্ট। আর আমরা সেখান থেকে একটা একটা করে নিয়ে যেটা সাজিয়ে রাখি সেটাই হচ্ছে একটা সর্টেড আইটেমস লিস্ট। আরো ক্লিয়ার করে বলি শোন। ধর, আমার ভাগে ৪টি কার্ড পরেছে এবং সেগুলো এভাবে আছে card_list = [4, 2, 3, 1]  এখন আমি সেগুলো পাওয়ার পর কি করবো? প্রথমে একটা কার্ড হাতে নিয়ে দেখবো সেটা কি বা তার প্রায়োরিটি কতো! এবং সেটিকে আমার বাম হাতে রেখে দিবো, তারপর বাকি যে ৩টি কার্ড আছে সেখান থেকে আবার একটা তুলবো এবং চেক করে দেখবো যে আগেরটা থেকে প্রায়োরিটি বেশী নাকি কম? যদি প্রায়োরিটি বেশী হয় তাহলে আগেরটি থেকে ডান পাশে রেখে দিবো অথবা প্রায়োরিটি কম হলে বাম পাশে রেখে দিবো। এভাবেই সব কার্ড গুলো সাজিয়ে নিবো তাই নয় কি? এবার আমি মাথা নাড়ালাম এবং বুঝেছি সেটার সম্মতি জানায়ে বললাম তার মানে দাঁড়াচ্ছে একটা আন-সর্টেড আইটেমস লিস্ট থেকে একটা একটা করে আইটেম/ইলিমেন্ট নিয়ে আরেকটা লিস্টে সর্টেডভাবে সাজানোই হচ্ছে ইন্সার্শন সর্ট এলগোরিদমের কাজ তাইনা হাবলু দা? হাবলু দা সম্মতি দিয়ে বললেন বুঝেছো তাহলে! কিন্তু একটা বিষয় মাথায় রাখবা ইন্সার্শন সর্ট সলগোরিদম কিন্তু খুব বেশী ইফিশিয়েন্ট সর্টিং এলগোরিদম না। সর্টিং এর জন্য অনেক গুলো এলগোরিদম আছে যেমন বাবল সর্ট, সিলেকশন সর্ট, মার্জ সর্ট, হিপ সর্ট ইত্যাদি আর ঐ এলগোরিদম গুলোর মতোই ইন্সার্শন সর্টটাও হচ্ছে একটা সর্টিং এলগোরিদম। আর সর্টিং এলগোরিদমের মধ্যে কোনটি বেশী ইফিশিয়েন্ট এবং কোনটি কখন ব্যবহার করা হয় সেটা পরে আলোচনা করবো আজকে আর না। চল তোকে এবার স্যুডো কোড বুঝাই দিয়ে পাইথনে সেটাকে ইমপ্লিমেন্ট করে দেখাই।

এলগোরিদমঃ

স্যুডো কোডঃ

সমাধানঃ

আউটপুটঃ

Sorted Prime list : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

বাইনারি সার্চ ইমপ্লিমেন্ট

হাবলু দা’র এক সিনিয়র ভাই তাকে একটা প্রাইম নাম্বারের অর্ডারড/সর্টেড লিস্ট হাতে ধরাই দিয়ে বলল এইটা বাইনারি সার্চ এলগোরিদম ব্যবহার সল্ভ করে দাও। আহা হাবলু দা সেটাকে হাতে পেয়েই লুতুপুতু ভাব নিয়ে মুচকি হাসি দিতে লাগলো। হাবলু দা অবশ্য ২টা কারণে হাসি আটকাতে পারতেছিলেন না। ১) প্রাইম নাম্বারের লিস্টটি অলরেডি সর্টেড। ২) বাইনারি সার্চতো তিনি কয়েকশতবার প্রাকটিস করেছেন!এবার কাহিনী শুরু বড় ভাই মুচকি হাসি দিয়ে বললেন আরে দাড়াও এতো খুশি হওয়ার কিছু হয়নি এখনো। সমস্যা সম্পুর্ন বর্ননা করি তারপর না হয় অট্টহাসি দিও! এই কথা শোনার পর হাবলু দা’র মনের ভিতরে কিঞ্চিৎ ভয় ঢুকে গেছে। আহারে আজকে কপালে বুঝি শনি আছে ভেবে ভেবে হাবলু দা চিন্তিত হয়ে পরলেন। আর ঐ দিকে বড় ভাই তার সমস্যার একটা নোট রেডি করতেছেন।

নোট তৈরি শেষে এবার তিনি হাবলু দা’কে ডেকে বললেন শোন সমস্যাটা খুব বেশী জঠিল কিছু না। খুবই সিম্পল তবে যদি তুমি সিম্পলভাবে চিন্তা করতে পারবো তাহলেই তুমি তুড়ি মেড়ে সল্ভ করতে পারবা। উহা শুনে হাবলুর দা’র তারই অজান্তে ফুড়ুৎ করে একটা আনন্দের হাসি দিয়ে ফেললেন। হাসিটার কারণ আমি তখনো বুঝিনি তবে এতোটুকু বুঝতে পেরেছিলাম যেকোন সমস্যার সমাধান করতে পারার মধ্যে একটা পৈশাচিক আনন্দও আছে।

এবার বড় ভাই হাবলু দা’কে সমস্যাটা বুঝিয়ে দিলেন এভাবেঃ

সমস্যাঃ ধর আমার একটা সর্টেড/অর্ডারড প্রাইম নাম্বারের লিস্ট আছে এখন আমি আমার ইচ্ছা মতো যেখনো একটা নাম্বার ইনপুট দিয়ে দেখতে চাই সেটি প্রাইম নাম্বার কিনা এবং যদি প্রাইম নাম্বার হয় তাহলে তার সামনে আরো কতোটি প্রাইম নাম্বার আছে তার একটা হিসাব যেন আমি জানতে পাই।

সমস্যাটি শোনার পর হাবলু দা প্রায় ৩০ সেকেন্ডের মতো চুপ করে থেকে তারপর বড় ভাইকে বললেন আমার কিছু প্রশ্নও আছে! বড় ভাই সানন্দে বললেন অবশ্যই! বল কি জানতে চাও?

আউটপুট কিভাবে দেখতে চাচ্ছেন? আউটপুট কি বুলিয়ানে দেখাতে হবে?

প্রশ্ন শোনার পর বড় ভাই তাকে বললেন, তুমি আউটপুট দেখাবা হচ্ছে কথায় যেমনঃ ৬৭ হচ্ছে প্রাইম নাম্বার এবং তার আগে এন সংখ্যক প্রাইম নাম্বার আছে। অন্যথায় দেখাবা ৬৭ প্রাইম নাম্বার নয়।

তারপর হাবলু দা বড় ভাইকে বললেন আচ্ছা ঠিক আছে আমি একটা কোল্ড কফি পান করে এসেই সমস্যা সমাধানে বসে যাবো। আমিতো আবার নাছোড় বান্দা তাই হাবলু দা’র পিছে পিছে চলে গেলাম। হাজারো হউক কোল্ড কফি বলে কথা 😛

কফি শেষে হাবলু দা তার টেবিলে বসে খাতা, পেন্সিল নিয়ে কি যেনো নোট করতেছেন। আমি আবার চুপচাপ থাকার ছেলে নই তাই জিজ্ঞাসা করেই ফেললাম আচ্ছা দাদা আপনি সমস্যা সমাধান করবেন কম্পিউটারে পেন্সিল, খাটা নিয়ে কি লিখতে বসলেন? হাবলু দা একটু রাগা রাগা ভাবে বললেন এখন বিরক্ত কইরোনা পরে বুঝাবোনি। আমিও ভয়ে গুটিস্যুটি হয়ে চুপটি করে করে পাশে বসে রইলাম।

পাশে বসে থেকে দেখতেছি হাবলু দা তার খাটায় লিখে রেখেছেনঃ

1) Let min_num = 0 and max_num = n-1

2) Compute the guess as the average of max_num and min_num and make sure it is an integer result.

3) If primes_list[guess] equals target, then stop. Yes found it! Return the result.

4) If the guess was too low, that is, primes_list[guess] < target, then set min_num = guess + 1.

5) Otherwise, the guess was too high. Set max_num = guess – 1.

6) Go back to step 2

সমাধানঃ

আউটপুটঃ

ভালো জিপিএ/সিজিপিএ পাওয়ার জন্য ৫ টি টিপস/সিক্রেট

সাধারণত শিক্ষা প্রতিষ্ঠানে ভালো মার্কস, ভালো জিপিএ/সিজিপিএ এর উপর নির্ভর করেই ভালো ছাত্র খারাপ ছাত্র নির্বাচন/নির্ধারণ করা হয়ে থাকে। যেমনটা চাকুরীর ক্ষেত্রে বেতন :P। যদিওবা ব্যতিক্রম আছে কিন্তু ব্যতিক্রম উদাহরণ হিসেবে বলা উচিৎ না। ছাত্রাবস্থায় ভালো রেজাল্ট করা যেমন সহজ একটা বিষয় তেমনি কঠিন হচ্ছে খারাও রেজাল্ট করা। সত্যি বলতে কি খারাপ রেজাল্ট করাটাই কঠিন ব্যাপার, ভালো রেজাল্ট করা অনেক সহজ যদিওবা আমরা সেটার উলটা কথা বলি 😉

আচ্ছা বেশি কথা না বাড়িয়ে চলুন পড়ে নেওয়া যাক সেই পাঁচটি গোপন রহস্যজনক তথ্য!

১) ক্লাসে উপস্থিত থাকাঃ ভালো রেজাল্ট বা ভালো জিপিএ/সিজিপিএ অর্জনের জন্য ক্লাসে উপস্থিত থাকাটাও একটা গুরুত্তপুর্ন বিষয় যা আপনাকে পরীক্ষার সময় অনেক সহায়তা করে থাকবে। ক্লাসে উপস্থিত থাকতে পারলে শিক্ষকগণের সাথে ভালো ভালো সম্পর্ক তৈরি হয়, বন্ধুদের সাথে ভালো সম্পর্ক তৈরি হয়। আর সবচেয়ে মজার ব্যাপার হচ্ছে উপস্থিত মার্ক এটলিস্ট ৯০% পাওয়ার সুযোগ থাকে।

২) ক্লাসে ভালো পার্ফর্মেন্স দেখানোঃ  ক্লাসে ভালো পার্ফর্মেন্স দেখানোর জন্য সবচেয়ে ভালো উপায় হচ্ছে ক্লাসে নিয়োমিত উপস্থিত থাকতে হবে। শিক্ষক যে বিষয়ে যেই যেই নোট, ই-বুকসহ অন্যান্য যেসব তথ্য প্রদান করে থাকেন সেগুলা মনোযোগ দিয়ে সংগ্রহ করে নিতে হবে এবংবাসায় গিয়ে সেগুলা নিয়ে অবশ্যই স্টাডি করতে হবে। যদি কোন টপিকস বুঝতে না পারেন বা বুঝতে সমস্যা হয় তাহলে প্রথমেই আগে গুগল করে দেখুন বিষয়টা কিভাবে আয়ত্ত করা যায়। তারপর অন্য ক্লাসমেটদেরকে জিজ্ঞাসা করুন। তারপরেও পরিষ্কার ধারণা পাওয়া না গেলে অবশ্য অবশ্যই শিক্ষকের কাছে চলে যেতে হবে এবং তাঁর সাহায্য কামনা করতে হবে। এছাড়াও কুইজ টেস্ট, ক্লাস টেস্ট এর জন্য নিজেকে প্রতিদিনই প্রস্তুত রাখতে হবে। কারণ এখানেও কিন্তু মার্কিং সিস্টেম আছে।

৩) এসাইনমেন্ট ভালোভাবে তৈরি করতে হবেঃ শিক্ষক যখন কোন এসাইনমেন্ট এসাইন করে দেন তখন সেই টপিকস এর উপর তিনি ক্লাসে পুর্নাঙ্গো/কিছুটা হলেও ধারণা দিয়ে থাকেন তারপর তিনি এসাইনমেন্ট তৈরি করে ক্লাসে নিয়ে যেতে বলেন। তাই যখন কোন এসাইনমেন্ট এসাইন করা হয় তখন যদি কোন টপিকস বুঝতে সমস্যা হয় তাহলে অবশ্যই শিক্ষকের থেকে তা পরিষ্কার ধারণা নিয়ে নিতে হবে অন্যথ্যায় নিজেকে সমদ্র পৃষ্ঠে আবিষ্কার করলেও অবাক হওয়ার কিছু থাকবেনা। তাই এসাইনমেন্ট তৈরি করতে বসার আগে টপিকস এর উপর খুবই পরিষ্কার একটা ধারণা রাখতেই হবে। যদি ধারণা পরিষ্কার থাকে তাহলে এসাইনমেন্ট তৈরি করার সময় অবশ্যই তা কেয়ারফুলি তৈরি করে শিক্ষককে যথাযথ সময়ের মধ্যেই প্রদান করতে হবে অন্যথায় এসাইনমেন্টের উপর যে মার্ক থাকে তা থেকে কিঞ্চিৎ হলেও বঞ্চিত হবেন এতে কোন সন্দেহ নাই। তাই এসাইনমেন্ট তৈরি করুন ভালোভাবে এবং ভালোমানের।

৪) প্রেজেন্টেশনে ভালো করতে হবেঃ কম বেশি প্রতিটা সাব্জেটের উপরই সিলেবাস শেষে শিক্ষক আশা করে থাকেন এতোদিন তিনি যেসব টপিকস নিয়ে কথা বলেছেন, বার বার বোঝানোর জন্য সর্বাত্তক চেষ্টা করেছেন সেগুলা ছাত্ররা ঠিক কতোটুকু নিতে পেরেছেন বা বুঝতে পেরেছেন তারই একটা সাধারণ পরীক্ষা মাত্র। আপাতত দৃষ্টিতে মনে হতেই পারে যে প্রেজেন্টেশনে আবার কি এমন হাটি ঘোড়া আছে? কিন্তু ভাইয়া একটু থামেন প্রেজেন্টেশন খুবই সিম্পল একটা বিষয় হলেও ইহার মাধ্যমে আপনাকে অনেকখানিই পরীক্ষা করে নেওয়া সম্ভব। যেমন আপনি ক্লাসে বসে ঝিমাইছেন? নাকি পিছনে বন্ধুদের সাথে খোশ গল্পে মেতে ছিলেন? সেটাও বুঝা যায় কিন্তু 😛 আর সবচেয়ে মজার বিষয় হচ্ছে এখানেও কিন্তু মার্কিং থাকে। অর্থাৎ প্রেজেন্টেশনের উপর যে মার্কস থাকে তা কিন্তু আপনি ১০০% অর্জন করে নিতে পারেন যদি আপনি খুবই সিন্সিয়ার হয়ে প্রেজেন্টেশন প্রদান করতে পারেন। আর প্রেজেন্টেশন দেওয়ার চেয়ে তৈরি করাটাই বেশি গুরুত্তপুর্ন। যদিওবা প্রেজেন্টেশন তৈরি করা থেকে প্রদান পর্যন্ত পুরাটাই গুরুত্তপুর্ন।

৫) পরীক্ষায় ভালোভাবে লিখতে হবেঃ পরীক্ষা সামনে চলে আসলেই অনেক মামুর বেটারা অনেকভাবেই ৩ নাম্বার(অজুহাত) হাত দেখানোকে একটা বাড়তি ভাব বলেই মনে করে থাকেন। যেমনঃ আমি মুখস্ত করতে পারিনা! আমি পড়ারসময় পাইনা! পড়তে বসলেই ঘুম চলে আসে! পড়ার চেয়ে অমুক করতেই বেশি ভালো লাগে ইত্যাদি ইত্যাদি।

আচ্ছা মামুর বেটারা এবার একটু মুল কথায় আসি। আরে ভাই আপনাকে চোখ বন্ধ করে মুখস্ত করতে বলেছেন কে? একটু চোখ খোলা রেখে পড়লেইতো কাজে দেয়। আর তাছাড়া মুখস্থ করে পরীক্ষা দেওয়া আর নকল করে পরীক্ষা দেওয়া সমান কথা। তাই মুখস্থ করে পরীক্ষা দেওয়ার চেয়ে টপিকসসমূহ বুঝার চেষ্টা করুন! বাস্তবিক জীবনের সাথে রিলেট করে পড়ুন! তাহলে দেখবেন মুখস্থবিদের চেয়েও আপনি অনেক ভালোভাবে লিখতে পারবেন এবং ভালো মার্কসও অর্জন করতে পারবেন।

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

পরিশেষে আমি আশা রাখই আপনার সামনের সেমিস্টারের রেজাল্ট আগের চেয়ে অনেক ইম্প্রুভ করবে 🙂