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

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

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

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

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

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

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

হাবলু দা এবার বললেন আমাদের ভাগের ঐ এলোমেলো কার্ড  গুলোই হচ্ছে আন-সর্টেড আইটেমস লিস্ট। আর আমরা সেখান থেকে একটা একটা করে নিয়ে যেটা সাজিয়ে রাখি সেটাই হচ্ছে একটা সর্টেড আইটেমস লিস্ট। আরো ক্লিয়ার করে বলি শোন। ধর, আমার ভাগে ৪টি কার্ড পরেছে এবং সেগুলো এভাবে আছে 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

সমাধানঃ

আউটপুটঃ