প্রোগ্রামিং জগতে কোনোকিছুকে সাজানো বা সর্ট (sort) করার কাজটা আমাদের হরহামেশাই করতে হয়! লুপ ঘুরিয়ে ঘুরিয়ে এই কাজটি আমরা শুরুর দিকে করে থাকি,পরে যখন আরেকটু এডভান্স হয়ে যাই,তখন ধীরে ধীরে আরো এফিশিয়েন্ট কোড লিখে,এলগরিদম এপ্লাই করে আরো চমৎকার চমৎকার কোড লিখে ফেলি! আমি তোমাদের সাথে মোট  ৭ ধরণের সর্টিং এবং তার এলগরিদম নিয়ে গল্প গুজব করবো,একটু শেখানোরও চেষ্টা থাকবে তার মধ্যে! চলো লিস্টটা দেখে ফেলিঃ

১) Insertion Sort
২) Bubble Sort
৩) Selection Sort
৪) Counting Sort
৫) Merge Sort
৬) Quick Sort
৭) Radix Sort

আজ যেহেতু আমার প্রথম পর্ব সর্টিং জগতে,আমি ১ নম্বরের এলগরিদমটা নিয়েই গল্পগুজবে মেতে উঠতে চাই! তোমরা প্রস্তুত তো? প্রস্তুত হলেই ইঞ্জিন স্টার্ট করবো!

 

** বাচ্চাকাচ্চারা সব গাড়িতে উঠে গেলো। স্বশিক্ষার গাড়ি ইঞ্জিন স্টার্ট দিলো! **

গুগল থেকে মেরে দেয়া আমাদের গাড়ি

গুগল থেকে মেরে দেয়া আমাদের গাড়ি

 

আলোচনার মূল বিষয়বস্তু হচ্ছে Insertion Sort. নাম শুনেই মনে হচ্ছে,কোনো কিছু “Insert” করে করে এই Sorting এর যাবতীয় কাজ সেড়ে ফেলতে হবে!! আসল ব্যাপারটিও তাই। আমরা একটি অ্যারেকে সর্ট করবো কিভাবে জানো? প্রথমে পুরো অ্যারেটাকে দু”টো ভাগে ভাগ করে ফেলবো। একটা ভাগ থাকবে সর্টেড,আরেকটা থাকবে আনসর্টেড। আনসর্টেড অ্যারে থেকে একটা একটা করে এলিমেন্ট নিয়ে এসে আমরা সর্টেড অ্যারেটার এমন একটা পজিশনে ইনক্লুড করে দিবো,যাতে অ্যারেটা তার ” সর্টেড ” ধর্ম বজায় রাখতে পারে! কি কুল ( ঠাণ্ডা?! ) আইডিয়া,তাইনা?

আচ্ছা,চলো কিছু উদাহরণের সাহায্যে অসাধারণ সহজ এই এলগরিদমটা আমরা দেখে আসিঃ

একটি অ্যারে দেখতে পাচ্ছি নিচের বক্সটায়ঃ

 

1

 

আমি এবার করবো কি,আমরা যে গাড়িটায় করে যাচ্ছি,সে গাড়িটা দিয়ে এই অ্যারের বক্সটাকে একটা ধাক্কা দিয়ে ভেঙ্গে ফেলবো! তবে ভাংবো কোথায়? :/ শুরুতে,শেষে নাকি মাঝে? কোথায় ভাংলে দুইটা অ্যারেতে এই অ্যারেটা বিভক্ত হবে,যার একটা অ্যারে থাকবে ”Sorted” !

খুবই সহজ প্রশ্ন,অ্যারেটার শুরুর দুইটা এলিমেন্টের মাঝ বরাবর গাড়ি চালিয়ে ভেঙ্গে দিবো! একটা উপাদান নিয়ে আমাদের সর্টেড অ্যারেটা তৈরী হবে!,তারপর আনসর্টেড অ্যারেটা থেকে একটা একটা করে এলিমেন্ট নিয়ে নিয়ে,সর্টেড অ্যারেটায় পুশ করতে থাকলে আর সেটাকে ব্যালেন্স করে করে আবার সর্টেড করে ফেলতে পারলেই আমাদের কাজ শেষ! 😀

1 - Copy

এবার আমরা করবো কি,Unsorted Array টা থেকে একটা একটা করে এলিমেন্ট তুলে নিয়ে বাম পাশের Sorted অ্যারেতে নিয়ে রাখবো এমনভাবে,যাতে বামপাশের অ্যারেটা তারপরেও Sorted থাকে। Unsorted অ্যারেটার প্রথম এলিমেন্ট টা হচ্ছে 3 , একে ধরে টেনে নিয়ে Sorted অ্যারেতে প্রবেশ করাতে চাইলে, 5 এর আগে প্রবেশ করালেই Sorted অ্যারেটা তার নামের সার্থকতা বজায় রাখবে!

 

1 - Copy

দেখো,বুঝতে পারলে তো কি করলাম? এভাবে পুরো Unsorted অ্যারেটার প্রতিটা এলিমেন্ট নিয়ে নিয়ে আমরা অ্যারেটাকে সর্ট করে ফেলবো। চলো বাকি স্টেপগুলো ও দেখে আসিঃ

1 - Copy

পরের ধাপ। এবার আসবে 17

1 - Copy

এবার পালা -5 এর,বেচারা চলে যাবে একেবারে শুরুতে,বাচ্চা কাচ্চারা শুরুতে থাকলেই ভালো!

1 - Copy

এবার আসবে 6. এই লোক ঢুকবে হচ্ছে 17 এর ঠিক আগে।

1 - Copy

এবার আসবে 2 . এই লোক ঢুকবে 3 এবং 1 এর মাঝে গিয়ে!

 

1 - Copy

এবার বাকি দুইজনকেও একইভাবে বা দিকে নিয়ে আসি।

 

সর্টিং শেষ!

হয়ে গেলো আমাদের Sorting! এটিই মূলত Insertion Sort এর মূল কারুকাজ।

 

Complexity Analysis:  

Insertion Sort প্রথমে অ্যারের শুরুর উপাদানটাকে আলাদা করে ফেলে,তারপর একটা একটা করে পরবর্তী উপাদানগুলো নিয়ে কাজ করা শুরু করে। এখানে একটা লুপ লাগবে,যার Complexity O(n).

আরেকটা লুপ Sorted Array টা পুরোটা চেক করে Unsorted Array টা থেকে উপাদান নিয়ে বসাবে। Sorted Array প্রথম উপাদানের জন্য চেক করতে ধাপ লাগবে ১টি,পরের আরেকটি উপাদানের জন্য চেক করতে হাইয়েস্ট ধাপ লাগবে ২টি,এভাবে n-size এর একটা গোটা অ্যারে চেক করতে ধাপ লাগবে n-টি। তাহলে গড়ে ধাপ লাগছে n/2 টি এবং এখানে আরো O(n/2) টাইম লেগে যাচ্ছে।
ধরে নিই , Compare করতে কন্সট্যান্ট টাইম ”k” খরচ হচ্ছে।
তাহলে মোট সময় লাগছে তাহলে O(n * n/2 * k) যেটাকে O(n^2) বলা চলে।

অ্যারে সাইজ 10^4 এর চাইতে বেশি হলে এই এলগরিদম দিয়ে কাজ করলে তুমি টাইম লিমিট খেতে পারো। এর চাইতে বেটার এলগরিদম রয়েছে যেমন Quick Sort,Merge Sort, যার কেউ নাই তার Built-in Sort ইত্যাদি। তবে Counting Sortএবং Radix Sort ও অনেক দ্রুত কাজ করতে পারে।

Simplicity এর দিক থেকে Insertion Sort আমার অনেক পছন্দের!

কোডঃ

#include <bits/stdc++.h>
using namespace std;

void InsertionSort(int *a,int length)
{
    int i,j;
    for (i = 1; i < length; i++)
    {
        for (j = i; j > 0; j--)
        {
            if (a[j] < a[j-1])
            {
                swap(a[j],a[j-1]);
            }
            else break;
        }
    }

}

int main()
{
    int ara[1000];
    int length;
    cin >> length ;
    for(int i=0; i<length; i++) cin >> ara[i];
    InsertionSort(ara,length);
    for(int i=0; i<length; i++) cout << ara[i] << ' ';
    return 0;
}

 

Notes:

১) তোমরা চাইলে descending order এও সর্ট করতে পারতে এই এলগরিদম এর সাহায্যে। কনডিশনে কেবলমাত্র less than এর বদলে greater than দিয়ে দিলেই কাজটা হয়ে যায়।
২) তোমরা চাইলে এই এলগরিদমের সাহায্য স্ট্রিংকেও সর্ট করে ফেলতে পারবে!
৩) একটি “প্রায়” সর্টেড অ্যারেকে সর্ট করার জন্য সবচেয়ে ভালো কাজ করবে এই Insertion Sort. তাই একে কিন্তু অবহেলা করা যাবেনা!

আজকের মতো এই পর্যন্তই! ডাটা স্ট্রাকচার নিয়ে একটি সিরিজ করার ইচ্ছা আছে। তোমাদের / আপনাদের সাড়া পেলে সে ব্যাপারে আগাবো। ধন্যবাদ।