যন্ত্রগণকের যন্তর মন্তর - ৩

পর্ব ১, পর্ব ২
সাত্তার সারের ভাত ঘুম (সাজানো/সর্টিং)

শেষমেশ ভাত ঘুমটা আর জুত করে দেয়া গেলোনা ...

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

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

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

সময় হাতে অল্প, এর মধ্যে ৫০টা বাঁদর ছাত্রকে কীভাবে তিনি উচ্চতার ভিত্তিতে সাজাবেন?

----

আসুন, আজ দেখা যাক, সাত্তার স্যারকে আমরা কীভাবে সাহায্য করতে পারি ...

সর্টিং বা বাছাইকরণ

বাছাই করা, অর্থাৎ ক্রমানুসারে সাজানো তথ্য বিশ্লেষণের একটি মৌলিক সমস্যা। এক গাদা সংখ্যাকে ছোট থেকে বড়, কিংবা বড় থেকে ছোট, অথবা অনেকগুলো নামকে বর্ণানুক্রমিকভাবে সাজানো – এরকম সমস্যা আমাদের প্রতিনিয়তই সমাধান করতে হয়। কম্পিউটার বিজ্ঞানে এই সমস্যাটির সমাধানের কৌশলগুলোকে বলে সর্টিং অ্যালগরিদম। আজ আমরা দেখবো এই সর্টিং এর কিছু সহজ কৌশল।

সিলেকশন সর্ট

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

ধরা যাক, সাত্তার স্যারের সামনে আছে রফিক, শফিক, দেবকান্ত, ফারুক, জুয়েল, ও হিমাদ্রি। এদের উচ্চতা একেক রকম, রীতিমতো বাটকু শফিক যেমন আছে, সেরকম ঢ্যাঙা গোছের ফারুকও আছে। এদের উচ্চতাগুলো, ইঞ্চিতে, ধরা যাক, (৬৩, ৫৫, ৬৫, ৫২, ৭১, ৫৬)।

তাহলে প্রথম ধাপে আমরা পেলাম সবচেয়ে বেঁটে হলো শফিক, অর্থাত ছোট সংখ্যা, ৫২। শফিককে সাত্তার স্যার বললেন মাঠের মধ্যে লাইনের শুরুতে দাঁড়াতে। (ভেঙচি কাটা দেখে ফেলাতে বাড়তি শাস্তি হিসাবে কান ধরে দাড় করিয়ে রাখলেন)। যাহোক, অংকের হিসেবে ব্যাপারটা দাঁড়ালো এরকম, আমাদের হাতের তালিকার শুরুতে রাখলাম [৫২]। বাকি সংখ্যার তালিকাটা হলো (৬৩, ৫৫, ৬৫, ৭১, ৫৬), আর তার মধ্যে সবচেয়ে ছোট হলো ৫৫। সেটাকে হাতের তালিকার পেছনে রাখলে হয়, [৫২, ৫৫]।

বাকি সংখ্যার তালিকা (৬৩, ৬৫, ৭১, ৫৬), সেখানকার ক্ষুদ্রতম সংখ্যা ৫৬। তাকে বাছাই তালিকার পেছনে দিলে সেটা হয় [৫২, ৫৫, ৫৬]।

বাকি সংখ্যার তালিকা (৬৩, ৬৫, ৭১), সেখানকার ক্ষুদ্রতম সংখ্যা ৬৩। তাকে বাছাই তালিকার পেছনে দিলে সেটা হয় [৫২, ৫৫, ৫৬, ৬৩]।

বাকি সংখ্যার তালিকা (৬৫, ৭১), সেখানকার ক্ষুদ্রতম সংখ্যা ৬৫। তাকে বাছাই তালিকার পেছনে দিলে সেটা হয় [৫২, ৫৫, ৫৬, ৬৩, ৬৫]।

আর বাকি রইলো ৭১, (ক্লাসের সবচেয়ে ঢ্যাঙা ছোকরা গুঁফো ফারুক, তার উচ্চতা এখনই কলেজে পড়া ছেলেদের মতো!!)। ৭১ সেটা তালিকার সবচেয়ে বড় সংখ্যা, তাকে বাছাই তালিকার পেছনে জুড়ে দিলে পাই [৫২, ৫৫, ৫৬, ৬৩, ৬৫]। ব্যস, বড় থেকে ছোটতে সাজানো হয়ে গেলো তালিকাটা।

আরেকটা উদাহরণ দেখা যাক নিচের ছবিতে (উৎসঃ উইকিপিডিয়া) -

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

এর চেয়ে দ্রুতও নিশ্চয় কাজটা করা সম্ভব? ৫০টা বাঁদর ছেলেকে এক এক করে এমন করে সাজাতে গেলে সারা দিন লাগবে, তাই সাত্তার স্যার এবার ক্লাসের ফার্স্ট বয় পার্থ, তাকে ডেকে কাজটা ধরিয়ে দিলেন। উনার আবার দুপুরের ভাতঘুমটা পেয়ে বসেছে।

বাবল সর্ট বা বুদ্বুদ বাছাই

পানি বা সাবান পানির মধ্যে স্ট্র ডুবিয়ে বুদবুদ বানিয়েছেন ছেলেবেলায়? কিংবা এখনো? যদি করে থাকেন তাহলে হয়তো দেখেছেন, বড় বুদবুদ অনেক দ্রুত ভেসে উঠে?

পার্থর মাথায় এলো এই বুদ্ধিটা, এক এক করে কে সবচেয়ে ছোট তা বের না করে অন্য পদ্ধতি খাটাবে। লম্বু কাউকে পেলেই লাইনের পেছনের দিকে ঠেলে দেবে।

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

আবারও উদাহরণ হিসাবে (৬৩, ৫৫, ৬৫, ৫২, ৭১, ৫৬) তালিকাটা দেখা যাক।

প্রথম দুইজনের উচ্চতা ৬৩ ও ৫৫, কাজেই লম্বু ৬৩কে দ্বিতীয় স্থানে পাঠানোতে তালিকাটা দাঁড়ালো (৫৫, ৬৩, ৬৫, ৫২, ৭১, ৫৬)। এবারে দ্বিতীয় ও তৃতীয় জনের জোড়া (৬৩, ৬৫) এর মধ্যে ৬৫ লম্বু, কাজেই জায়গা বদলের দরকার নাই। তার পরের জোড়া (৬৫, ৫২) কে জায়গা বদল করে পাই (৫৫, ৬৩, ৫২, ৬৫, ৭১, ৫৬)। তার পরের জোড়া (৬৫, ৭১) ঠিক আছে। সর্বশেষ জোড়া (৭১, ৫৬) কে জায়গা বদল করানোতে পাওয়া গেলো (৫৫, ৬৩, ৫২, ৬৫, ৫৬, ৭১)।

এবার দ্বিতীয় পর্যায়ে একই কাজ শুরু থেকে করতে হবে, কিন্তু সবশেষের জায়গার লম্বু ফারুককে বাদ দিয়ে,

(৫৫, ৬৩, ৫২, ৬৫, ৫৬, ৭১) -> (৫৫, ৬৩, ৫২, ৬৫, ৫৬, ৭১) (১ম দুইজন ঠিক আছে)

(৫৫, ৬৩, ৫২, ৬৫, ৫৬, ৭১) -> (৫৫, ৫২, ৬৩, ৬৫, ৫৬, ৭১) (জায়গাবদল)

(৫৫, ৫২, ৬৩, ৬৫, ৫৬, ৭১) -> (৫৫, ৫২, ৬৩, ৬৫, ৫৬, ৭১) (ঠিক আছে)

(৫৫, ৫২, ৬৩, ৬৫, ৫৬, ৭১) -> (৫৫, ৫২, ৬৩, ৫৬, ৬৫, ৭১) (জায়গাবদল)

এবার ৩য় পর্যায়ে একই কাজ শুরু, কিন্তু সবশেষের লম্বু ফারুক, আর তার আগের হিমাদ্রীকে বাদ দিয়ে।

(৫৫, ৫২, ৬৩, ৫৬, ৬৫, ৭১) -> (৫২, ৫৫, ৬৩, ৫৬, ৬৫, ৭১) (জায়গাবদল)

(৫২, ৫৫, ৬৩, ৫৬, ৬৫, ৭১) -> (৫২, ৫৫, ৬৩, ৫৬, ৬৫, ৭১) (ঠিক আছে)

(৫২, ৫৫, ৬৩, ৫৬, ৬৫, ৭১) -> (৫২, ৫৫, ৫৬, ৬৩, ৬৫, ৭১) (জায়গাবদল)

এবার ৪র্থ পর্যায়েও একই কাজ শুরু, কিন্তু শেষের তিনজনকে বাদ দিয়ে। এভাবে করতে থাকলে আর দুই ধাপ পরেই আমরা পাবো সাজানো তালিকাটি, (৫২, ৫৫, ৫৬, ৬৩, ৬৫, ৭১)।

বাবল সর্টের অ্যানিমেশন

পার্থ অবশ্য এতো দূর যেতে পারেনি। স্যার একটু তন্দ্রাতে যেতেই ফারুক পার্থকে মনের সুখে কিছুক্ষণ গাট্টা দিলো। আঁতেল পোলার মাতব্বরী এই রোদে আর কাঁহাতক ভালো লাগে।

শোরগোল শুনে সাত্তার স্যারের ঘুমটা গেলো ভেঙে। এখনো কাজ হয়নি দেখে মেজাজ সপ্তমে চড়লো, তাই এক রাউন্ড শাস্তি শেষে দায়িত্বটা এবার দেঁড়েল কুদ্দুসকেই দিলেন।

মার্জ সর্ট বা জোড়া বাছাই

কুদ্দুস পড়ায় লবডঙ্কা হলেও কাজের বুদ্ধি প্রখর। বাবা দানু মিঞা সওদাগরের খাতুনগঞ্জের আড়তে বসতে হয়না এখনো, কিন্তু সেখানকার হালচাল ছোটবেলা থেকে দেখে আসাতে এই ধরণের কাজগুলো সহজে করে ফেলতে পারে। কেবল পরীক্ষার খাতাতেই কিছু লিখতে ইচ্ছে করে না। এই নিয়ে ২ বার ফেল করে ক্লাস এইটেই আটকে আছে।

যাহোক, কুদ্দুসের মাথায় এলো, এতো ঝামেলা না করে কাজটাকে ছোট ছোট অংশে ভাগ করে ফেলা যাক। যেমন, আগের উদাহরণের তালিকাটা দেখা যাক। (৬৩, ৫৫, ৬৫, ৫২, ৭১, ৫৬) এই তালিকাটা এক বারে সাজানো কঠিন। তাই কুদ্দুস প্রথমেই এই তালিকাকে দুই ভাগে ভাগ করে ফেললো (৬৩, ৫৫, ৬৫) আর (৫২, ৭১, ৫৬)।

বুদ্ধিটা হলো, এই দুইটা তালিকাকে প্রথমে সাজিয়ে ফেলবে, তার পর এদের দুই তালিকাকে একসাথে জোড়া লাগাবে।
(৬৩, ৫৫, ৬৫) তালিকাটাকে কীভাবে সাজাবে? একই রকম, দুই ভাগে ভাগ করে ফেলা হলো। মাঝের জনকে তো আর কাটা যায় না, তাই তালিকাটা না হয়, (৬৩, ৫৫) আর (৬৫) এভাবে ভাগ হলো।

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

ব্যাস, শুরুর তালিকাটা গুছানো হয়ে গেলো, পরের ৩ জনের তালিকাটাও একইভাবে গুছিয়ে পাওয়া গেলো (৫২, ৫৬, ৭১)।

এবার কুদ্দুসের হাতে দুটো দল, (৫৫, ৬৩, ৬৫), আর (৫২, ৫৬, ৭১)। এদেরকে জোড়া লাগানোর কাজ শুরু করলো কুদ্দুস।

(৫৫, ৬৩, ৬৫), (৫২, ৫৬, ৭১), [ ] -> (৫৫, ৬৩, ৬৫), (৫৬, ৭১), [৫২] (৫৫ আর ৫২ এর মধ্যে ৫২ ছোট)

(৫৫, ৬৩, ৬৫), (৫৬, ৭১), [৫২] -> (৬৩, ৬৫), (৫৬, ৭১), [৫২, ৫৫] (৫৫ আর ৫৬ এর মধ্যে ৫৫ ছোট)

(৬৩, ৬৫), (৫৬, ৭১), [৫২, ৫৫]->(৬৩, ৬৫), (৭১), [৫২, ৫৫, ৫৬]

(৬৩, ৬৫), (৭১), [৫২, ৫৫, ৫৬] -> (৬৫), (৭১), [৫২, ৫৫, ৫৬,৬৩]

(৬৫), (৭১), [৫২, ৫৫, ৫৬,৬৩]-> ( ), (৭১), [৫২, ৫৫, ৫৬, ৬৩, ৬৫]

( ), (৭১), [৫২, ৫৫, ৫৬,৬৩]-> ( ), ( ), [৫২, ৫৫, ৫৬, ৬৩, ৬৫, ৭১]

ব্যাস, গুছানো শেষ। আর এতে ঝামেলাও কম হলো। ঠিক কতোটা কম, কুদ্দুস নিজেও টের পায়নি, কিন্তু আমরা অংক করে দেখতে পারি, ক জন ছাত্র থাকলে তাদের সাজাতে সময় লাগবে ক x log(ক) সময়, যা আগের দুটো পদ্ধতির চাইতেই অনেক কম।

মার্জ সর্টের বিভিন্ন ধাপের আরেকটি উদাহরণ দেখা যাক নিচের ছবিতে (সূত্রঃ উইকি),

পাদটীকা-

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