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

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

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

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

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

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

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

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