প্রোগ্রামিং সিরিজ : Sort Algorithm

September 25, 2018 ...
পুরোটা পড়ার সময় নেই? ব্লগটি একবার শুনে নাও।

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

বেশির ভাগ মানুষ দেখে, না দেখার ভান করে চলে যাচ্ছিল। কিন্তু একজন বয়স্ক মুরব্বি এসে যোগ দিলেন। উনি পা দিয়ে মাটির দলা ভেঙে রাস্তার মাঝখানটা উঁচু করে দিতে লাগলেন। যাতে রাস্তার সাইডের দিকে ঢালু অ্যাঙ্গেল হয়ে বৃষ্টির পানি সাইডে নেমে যায়। এক-দেড় ঘণ্টা পরে আরও কয়েকজন হেল্প করতে এগিয়ে এল। এভাবে তিন-চার ঘণ্টা কাজ করার পরে রাস্তা ঠিক হয়ে যায়। সেই রাস্তায় কাদায় পিছলে পড়া চিরতরে বন্ধ হয়ে যায়।

|  sort অ্যালগরিদম |  array সিরিয়াল করে সাজানো |

ভেঙে যাবে sort-এর বাটি

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

তুই হয়তো খেয়াল করছ নাই। তবে প্লেটের টুকরা ওঠানোর সময় তুই বড় টুকরাগুলা আগে তুলছিলি। বড় টুকরাগুলা ওঠানোর পর মাঝারি সাইজেরগুলা তুলছিলি। সেগুলা তুলে ফেলার পর ছোট ছোট টুকরাগুলা তুলছিলি। আর ছোট টুকরাগুলা তোলা হয়ে যাওয়ার পর মিনি মিনি টুকরাগুলা তুলছিলি। তার মানে তুই বড় টুকরা থেকে ছোট টুকরা সিরিয়াল অনুসারে তুলছিলি।

আবার টেবিলের ওপরে বইখাতা গোছাতে গেলে নিজের অজান্তেই বড় বইগুলা নিচের দিকে, ছোট বইগুলা ওপরের দিকে রাখছ। গ্রুপ ফটো তোলার সময়ও উচ্চতায় ছোট পোলাপান সামনে আর লম্বু পোলাপান পিছনের দিকে থাকে। মানিব্যাগে টাকা রাখার সময় ছোট নোটগুলা সামনের দিকে আর বড় নোটগুলা পিছনের দিকে থাকে।

এই সিরিয়াল করে সাজানোর কাজটাকে ইংরেজিতে বলতে পারস sort করা। আর ধাপে ধাপে sort করাকে প্রোগ্রামিংয়ের ভাষায় sorting অ্যালগরিদম বলে। অর্থাৎ “sort” শব্দের সাথে “ing” যোগ করে sorting শব্দ বানাইছে। আর কিছু না।

ধর, একদিন ঘুম থেকে উঠে দেখস তুই বিশাল বড়লোক হয়ে গেছস। তোর কাছে 500 টাকার নোট, 50 টাকা নোট, 100 টাকার নোট, এমনকি 10 টাকা, 20 টাকার নোটও আছে। যেহেতু অনেকগুলা টাকার নোট আছে, সেহেতু নোটগুলাকে notes নামক একটা array-এর মধ্যে রাখলি নিচের মতো করে—

var notes = [500, 50, 10, 20, 100];

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

তুই খুঁজেটুজে দেখলি সবচেয়ে ছোট নোট হচ্ছে 10 টাকার নোট। তাই 10 টাকার নোটকে সবার আগে অর্থাৎ প্রথম পজিশনে নিয়ে আসবি। এখন সমস্যা হচ্ছে প্রথম পজিশনে তো অলরেডি 500 টাকার নোট বসে আছে। সে কই যাবে? আপাতত এই 10 টাকা, 500 টাকার প্যাঁচাল চিন্তা করার আগে এ রোমান্টিক জার্নি বাই বাসের কথা চিন্তা করে আয়।         

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

একটু আগে 500 টাকার নোটের জায়গায় 10 টাকার নোটকে বসাতে গিয়ে যে ক্যাচাল লাগছিল সেটাও সহজেই বাসের সিট অদলবদল সিস্টেমে সমাধান করা যায়। অর্থাৎ বাসে যেমন সেই লোক তোর সিটে গিয়ে বসেছিল আর তুই তার সিটে গিয়ে বসেছিলি। এখানেও 10 টাকার নোট গিয়ে 500 টাকার পজিশনে বসবে। আর 500 টাকার নোট গিয়ে 10 টাকার পজিশনে গিয়ে বসবে। অর্থাৎ 500 টাকার নোট আর 10 টাকার নোট তাদের জায়গা অদলবদল করবে। এই অদলবদলের পর তোর notes নামক array-এর চেহারা দেখতে নিচের মতো হবে।  

notes = [10, 50, 500, 20, 100];

ওপরের array-এর দিকে খেয়াল করলে দেখা যায় সবচেয়ে ছোট নোট বা সবচেয়ে ছোট সংখ্যাটা তোর array-এর সবার প্রথম পজিশনে চলে আসছে। এখন তোর কাজ হচ্ছে বাকি যেসব নোট আছে, এর মধ্যে সবচেয়ে ছোট নোটটা খুঁজে বের করে সেটাকে সেকেন্ড পজিশনে বসানো। তুই খুঁজেটুজে বাকিগুলার মধ্যে সবচেয়ে ছোট 20 টাকার নোট। তাই 20-এর সাথে সেকেন্ড পজিশনে থাকা 50-এর জায়গা অদলবদল করে নিলি। তারপর notes নামক array-এর চেহারা দেখতে নিচের মতো হবে—

notes = [10, 20, 500, 50, 100];

বাকি থাকল তিনটা নোট। এই তিনটা নোটের মধ্যে সবচেয়ে ছোট 50। তাই 50-এর সাথে তৃতীয় পজিশনের অদলবদল করলি। তারপর বাকি থাকল দুইটা নোট 500 আর 100। এই দুইটার মধ্যে 100 ছোট। তাই 500-এর সাথে 100-এর জায়গা অদলবদল করলি। তাহলে তোর notes নামক arrayটা সিরিয়াল করে সাজানো বা sorting করা হয়ে যাবে। সাজানোর পর সেটা দেখতে নিচের মতো হবে।

notes = [10, 20, 50, 100, 500];

এতক্ষণ যা যা করলি, সেগুলা এক সাথে স্টেপ বাই স্টেপ দেখ—

ZsWDoi g6yn7afpVO82G ycCXsacqJirHxlzXs2 gbM51 F4U mZjF C9HW5MicV74uP 21F6ZHIDcSIvKWg1E549d2Hyag52 ETL4UB4cHLhRf4j3KjEgSNJ y8jC3fJ5DFUNtESjoFu0O Q

Selection sort

প্রোগ্রামার হওয়ার জন্য sorting-এর কনসেপ্ট বোঝা খুবই খুবই গুরুত্বপূর্ণ। এবং ভালো প্রোগ্রামার হতে হলে দুই-চারটা sorting অ্যালগরিদম নিজে নিজে বুঝে বুঝে কোডিং করার প্র্যাকটিস থাকতে হবে। একটু আগে তোর মানিব্যাগের টাকার নোটগুলা sort করার জন্য তুই যে পদ্ধতি বা অ্যালগরিদম ব্যবহার করছিলি সেটাকে বলে selection sort অ্যালগরিদম। কারণ sort করার সময় তুই বারবার এসে সবচেয়ে ছোটটা সিলেক্ট (select) করছস। তারপর সেটার জায়গা অদলবদল করছস। যখন সময় পাবি তখন www.habluderadda.com/concepts/sort-এ চলে যাবি তাহলে selection sort-এর কোডিং প্র্যাকটিস করতে পারবি।

ফ্রিতে পাওয়া sorting অ্যালগরিদম

বেশির ভাগ প্রোগ্রামিং ল্যাঙ্গুয়েজের মধ্যেই sort করার প্রোগ্রাম আগে থেকেই লেখা থাকে। সেগুলাকে কল করেই sort করে ফেলা যায়। তবে ভালো মানের প্রোগ্রামার হতে চাইলে sort প্রোগ্রাম কীভাবে কাজ করে সেটা বোঝা এবং কয়েকবার নিজে নিজে লেখা খুব গুরুত্বপূর্ণ। আর সেটা বুঝে ফেলার পর প্রোগ্রামিং ল্যাঙ্গুয়েজের দিয়ে দেওয়া sort ফাংশনকে কল করে কাজ চালানো কোনো ব্যাপারই না। ধর, তুই torkari নামক array-কে প্রোগ্রামিং ল্যাঙ্গুয়েজের দিয়ে দেওয়া ফাংশন দিয়ে sort করে ফেলতে চাস। তাহলে প্রথমেই arrayটা ডিক্লেয়ার করবি। তারপর নিচের মতো করে array-এর নাম লিখে ডট (.) চিহ্ন দিয়ে sort লিখবি। তারপর দুইটা প্রথম ব্র্যাকেট দিয়ে দিবি। তাহলেই তোর torkari নামক array sort হয়ে যাবে।

var torkari = [“korola”, “lau”, “alu”, “tomato”, “begun”];

torkari.sort();

বিশ্বাস না হলে, www.habluderadda.com/console-এ চলে যা, সেখানে টাইপ করে দেখ তাহলেই আউটপুট হিসেবে [“alu”, “begun”, “korola”, “lau”, “tomato”] দেখতে পাবি।

selection sort ছাড়াও আরও কয়েকটা sorting অ্যালগরিদম আছে। বড় বড় কোম্পানিতে ইন্টারভিউ দিতে গেলে সেগুলা নিয়ে প্রশ্ন করে। এই সব উচ্চতর sorting অ্যালগরিদমের মধ্যে bubble sort, merge sort, insertion sort, quick sort অন্যতম। এত কঠিন কঠিন নাম দেখে ভয় পাওয়ার কিছু নাই। এখন নামগুলা শুনে রাখ। পরে দরকার হলে গুগলে সার্চ দিয়ে শিখে ফেলতে পারবি।

Insertion sort NIQwVHMu3yaI0U8yyVW6AOXW52l6zb3rJRAvvKYtFNMu88sOJnZ8lJzlaMe yfBHgWEP8UMJoMoPALq1aKoWddjYGiPUvdVGtsHJm9X Vk4W Dd4c11hzbz68O2Xz9KGzaWpQBjACYt1RMo1Hw

যারা তাস খেলে বা তাস সম্পর্কে ধারণা আছে তাদের জন্য এই অ্যালগরিদমটা কিচ্ছু না। ধর তোরা চারজন কার্ড খেলতে বসছস। এখন তোকে একজন একটা একটা করে পাঁচটা কার্ড দিবে। আর কার্ড নেওয়ার সময় তুই চিন্তা করছস সিরিয়াল অনুসারে রাখবি। কোনটা কি টাইপের কার্ড সেটা চিন্তা না করে শুধু কার্ডের উপরে লেখা সংখ্যা অনুসারে সিরিয়াল করবি। ধর প্রথমেই তোকে 5 দিল। তুই সেটা হাতে রেখে দিলি। তারপর তোকে দিল 2; আর 2 যেহেতু 5-এর চেয়ে ছোট তাই 2 লেখা কার্ডটা 5-এর আগে রাখলি। তাইলে এখন তোর হাতে যে দুইটা কার্ড আছে এই দুইটা সিরিয়াল করে সাজানো হয়ে গেছে। কারণ তোর হাতে প্রথমেই আছে 2 লেখা কার্ড আর তারপর আছে 5 লেখা কার্ড।

এখন তোকে দিল 4 লেখা কার্ড। যেহেতু 4 সংখ্যাটা 2-এর চেয়ে বড় কিন্তু 5-এর চেয়ে ছোট। তাই 4 লেখা কার্ডকে 2 এবং 5 লেখা কার্ডের মাঝখানে রাখলি। তারপর দিল 10 লেখা কার্ড। আর 10 যেহেতু 2, 4, 5 সবগুলার চেয়ে বড়। তাই এটাকে সবার শেষে রাখলি। এরপর দিল 7 লেখা কার্ড। 7 হচ্ছে 5-এর বড় কিন্তু 10-এর ছোট। এই 7 কে 5 আর 10-এর মাঝখানে রাখলি। ব্যস, তোর সাজানো হয়ে গেল।

প্রতিবারই তুই একটা একটা করে কার্ড insert করতেছস। insert শব্দের মানে প্রবেশ করানো বা ঢোকানো। তাই এইটাকে insertion sort বলে।

তুই এখন selection sort এবং insertion sort কীভাবে করে জানস। তবে শুধু কনসেপ্ট জানলেই হবে না, কোডিংও জানতে হবে। সে জন্য যখন সময় পাবি তখন www.habluderadda.com/concepts/sort-এ চলে যাবি। সেখানে কয়েকটা জনপ্রিয় sorting অ্যালগরিদম কোডিংসহ আলোচনা করা আছে। সেগুলা প্র্যাকটিস করে করে পিষে ফেলবি।

নিজে নিজে কর

৯.১ : তোর পাঁচ সাবজেক্টের নম্বর দিয়ে result নামে একটা array ডিক্লেয়ার কর। তারপর সেই নম্বরগুলা selection sort দিয়ে sort করলে কোন স্টেপের পর কোন স্টেপ আসবে তা নিচে লিখ।  

উত্তর :

৯.২ : মাসের কোন কোন দিন ডেট করা লাগবে, সেটা তোর গার্লফ্রেন্ড ছোট ছোট টুকরা কাগজে করে লিখে দিচ্ছে। সেখানে একটা করে তারিখ লেখা আছে। সে এই সিরিয়াল অনুসারে দিচ্ছে— 13, 2, 29, 6, 23 । এখন তোর কাজ হবে এই তারিখের টুকরা কাগজগুলা সিরিয়াল অনুসারে insert কর যাতে insertion sort হয়ে যায়। নিচে সেই insert sort সিরিয়াল করে লিখ।  

উত্তর :

…ওপরের সাজানো-গোছানোর আলোচনা শুনে তুই তোর বাসায় ছড়ানো-ছিটানো সব জিনিস সিরিয়াল করে সাজিয়ে ফেললে ভাব পেটাতে www.habluderAdda.com/bolod/sort.html-এ চলে যা। সেখানে কেউ যদি প্রশ্ন করে তোর বাসা এত সুন্দর করে সাজানো-গোছানো হওয়া কীভাবে সম্ভব? তখন বুক ফুলিয়ে বলে দিবি, অসম্ভবকে সম্ভব করাই sorting-এর কাজ।

ঝংকার মাহবুবের অন্যান্য লেখা সম্পর্কে জানতে চলে যাও এই লিংকে!
ঝংকার মাহবুবকে ফলো করতে পারো ফেসবুক পেইজেও!


১০ মিনিট স্কুলের ব্লগের জন্য কোনো লেখা পাঠাতে চাইলে, সরাসরি তোমার লেখাটি ই-মেইল কর এই ঠিকানায়: write@10minuteschool.com

আপনার কমেন্ট লিখুন