সর্টিং এলগোরিদম (Sorting Algorithm)

Aug 17, 2013

সর্ট করা হল সহজ বাংলায় সাজানো। এই সাজানোটা বিভিন্নভাবে হতে পারে। কি সর্ট করছি এবং কি কাজে সর্ট করছি তার উপর নির্ভর করে কিসের ভিত্তিতে এবং কিভাবে সর্ট করা হবে। এটি হতে পারে কতগুলো নাম্বারকে ছোট থেকে বড় ক্রমানুসারে (Ascending Order) সাজানো। হতে পারে বড় থেকে ছোট ক্রমানুসারে (Descending Order) সাজানো। যদি শব্দ সাজাতে হয় তাহলে হতে পারে বর্ণমালায় অক্ষরের ক্রমানুসারে সজ্জা।

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

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

ফেসবুকে প্রায় ১.১৫ বিলিয়ন (১১৫ কোটি) ব্যবহারকারী রয়েছে (মার্চ ২০১৩ পর্যন্ত, উৎসঃ উইকিপিডিয়া)। এতোজন প্রকৃত ব্যবহারকারী না থাকলেও তাদের তথ্য তো ডাটাবেসে রাখতে হয়েছে। আমরা যখন সার্চ করি তখন কত সহজেই সেই ডাটা আমাদের সামনে চলে আসে। এছাড়া গুগলের কাছে কোটি কোটি ওয়েবসাইটের তথ্য রয়েছে। আমরা যেকোন কিছু সার্চ করলেই আমাদের সামনে সেই বিষয়ে বিভিন্ন সাইটের ঠিকানা চলে আসে। প্রাথমিকভাবে মনে হতে পারে এটা আর তেমন কি। কিন্তু কম্পিউটারের জন্য এতো তথ্য থেকে নির্দিষ্ট কিছু তথ্য খুঁজে বের করাটা অত্যন্ত কঠিন কাজ, যেহেতু তথ্যের সংখ্যা হাজার বা লাখে না, বিলিয়ন বিলিয়ন তথ্য! একারণে আমাদেরকে তথ্যগুলো সর্ট করতে হয়।

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

কিছু সর্টিং এলগোরিদম এবং তাদের কমপ্লেক্সিটি

নাম	বেস্ট কেস	এভারেজ কেস	ওর্স্ট কেস
সিলেকশন সর্ট	$$ n^{2} $$	$$ n^{2} $$	$$ n^{2} $$
বাবল সর্ট	$$ n $$	$$ n^{2} $$	$$ n^{2} $$
ইনসার্শন সর্ট	$$ n $$	$$ n^{2} $$	$$ n^{2} $$
কুইক সর্ট	$$ n\log n $$	$$ n\log n $$	$$ n^{2} $$
মার্জ সর্ট	$$ n\log n $$	$$ n\log n $$	$$ n\log n $$
হিপ সর্ট	$$ n\log n $$	$$ n\log n $$	$$ n\log n $$

পরবর্তি পর্বঃ বাবল সর্ট