সর্টিংঃ ইনসার্শন সর্ট

সর্ট বা sort করার মানে হলো, একটি নির্দিষ্ট ক্রম অনুসারে সসাজানো। যদি আমরা কোন ক্লাসের পরীক্ষার খাতা ১ রোল থেকে ৬০ রোল পর্যন্ত ক্রম অনুসারে সাজাই, তাহলে এটাকে সর্টিং বলা হবে। প্রায়ই আমাদের বিভিন্ন সংখ্যা সর্ট করার প্রয়োজন হয়, আসলে শুধু সংখ্যা নয়, স্ট্রিং, স্থানাঙ্ক, এরকম অনেক সর্ট করার প্রয়োজন হয়।

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

ইনসার্শন সর্ট (Insertion Sort)

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

ইনসার্শন সর্টিং এর অ্যালগোরিদমটি আগে দেখে নেওয়া যাকঃ

// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

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

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

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

আসলে যত কঠিন ভাবছো, ওত কঠিন না। চলো সহজ করে দিচ্ছি।

মনে করো তোমার (1…i-1) খাতাগুলো সাজানো আছে, তুমি i তম খাতা ঢুকাবে। তাহলে তোমাকে প্রথমে দেখতে হবে i-1 খাতাটি কি তোমার হাতে থাকা খাতার থেকে ছোট কি না? যদি ছোট হয়, তাহলে যেখানে আছে, সেখানেই রাখো, আর যদি না হয় তাহলে i-1 এ থাকা খাতাকে i এ আনো, আর এবার i-2 এর সঙ্গে মিলিয়ে দেখো। এভাবে একটির পর একটি তুলনা করতে থাকো। বিষয়টি ভালো করে বুঝতে নিচের উধাহরনটি ভালো করে দেখোঃ

প্রথমে আমরা একটি আনসর্টেড অ্যারে নিবো, যা দেখতে নিচের মতঃ

নিয়ম অনুযায়ী আমাদের প্রথম দুইটা এলিমেন্টস কম্পেয়ার করতে হবে।

যেহেতু ১৪ এবং ৩৩ অ্যাসেন্ডিং অর্ডারে আছে, তাই ধরেনি ১৪ সর্টেড সাবলিস্টে আছে।

এবার আমাদেরকে পরের দুটি এলিমেন্টস কম্পেয়ার করত এহবে, এক্ষেত্রে ৩৩ কে ২৭ এর সাথে তুলনা করবো।

আমাদের ঐ খাতা সর্টিং এর কথা মনে আছে? যেহেতু ৩৩ তার পরের সংখ্যা ২৭ থেকে বড়, মানে ৩৩ সঠিক জায়গা নেই।

যেহেতু ৩৩ বড় আর ২৭ ছোট, তাই এখানে সোয়াপিং করে ২৭ আগে এবং ৩৩ পরে নিয়ে যেতে হবে। দুইটি সংখ্যা অ্যাসেন্ডিং এ সর্ট করার পর ২৭ কে সর্টেড লিস্টে যোগ করতে হবে। তাহলে আমাদের সর্টেড লিস্টে এই মুহূর্তে আছে ১৪ এবং ২৭।

যেহেতু ১৪ এবং ২৭ সর্টেড, আমাদের পরের দুইটা এলিমেন্ট কম্পেয়ার করতে হবে, এক্ষেত্রে ৩৩ আর ১০।

আবারো ৩৩ তার সঠিক স্থানে নেই, মানে ৩৩ সর্টেড না।

একটু আগে আমরা ২৭ আর ৩৩ এর ক্ষেত্রে যেভাবে সোয়াপিং করে সর্টেড ক্রএছিলাম, এখানেও একই ভাবে ১০ কে সোয়াপ করে ৩৩ এর আগে নিয়ে আসবো।

এখানে কিন্তু ১০ কে সোয়াপ করে সামনে আনাতে ২৭ এবং ১০ আবার আনসর্টেড হয়ে গেছে।

আমাদের লিস্ট কে সর্টেড করতে তাই আমরা আবার ১০ কে সোয়াপিং করে ২৭ এর আগে নিয়ে আসবো।

একটু খেয়াল করে দেখো, সোয়াপিং এর জন্য আবারো আমাদের লিস্ট আনসর্টেড হয়ে গেছে, এখানে ১৪ আর ১০ আনসর্টেড হয়েছে।

যেহেতু আমরা ইনসার্শন সর্টিং করছি, তাই আবারো আমরা ১৪ এবং ১০ কে সোয়াপিং এর মাধ্যমে সর্ট করবো।

আমরা কিন্তু এই মুহূর্তে ৪টি সর্টেড আইটেমস পেয়ছি। এভাবে বাকি আইটেম গুলোর জন্যও উপরে দেখানো কাজ গুলো করলে, সব শেষে আমরা একটি সর্টেড লিস্ট পাবো, যার ফলাফল হবেঃ ১০, ১৪, ১৯, ২৭, ৩৩, ৩৫, ৪২ এবং ৪৪।

উপরের ধাপ গুলোর সমন্বয়ে অ্যালগোরিদমটি যদি আমি আমার মত করে লিখি তাহলে হবেঃ

Step 1 − If it is the first element, it is
already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the
sorted sub-list
Step 4 − Shift all the elements in the sorted
sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

আশাকরি ইনসার্শন সর্টিং তোমার কাছে এখন একদম ক্লিয়ার। এবার চলো কিভাবে কোডিং করে ইমপ্লিমেন্ট করতে পারো তা দেখা যাক।

সি দিয়ে ইমপ্লিমেন্ট করলে কোড গুলো হবেঃ

// C program for insertion sort
#include <stdio.h>
#include <math.h>
 
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 
// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
 
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    insertionSort(arr, n);
    printArray(arr, n);
 
    return 0;
}

আউটপুটঃ 5 6 11 12 13

আর যাদের মোটামুটি পাইথন জানা আছে, তাদের জন্যঃ

# Python program for implementation of Insertion Sort
 
# Function to do insertion sort
def insertionSort(arr):
 
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
 
        key = arr[i]
 
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
 
 
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
    print ("%d" %arr[i])

আউটপুটঃ 5 6 11 12 13

আমরা চাইলে জাভা দিয়েও ইনসার্শন সর্টিং ইমপ্লিমেন্ট করতে পারিঃ

// Java program for implementation of Insertion Sort
class InsertionSort
{
    /*Function to sort array using insertion sort*/
    void sort(int arr[])
    {
        int n = arr.length;
        for (int i=1; i<n; ++i)
        {
            int key = arr[i];
            int j = i-1;
 
            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }
 
    /* A utility function to print array of size n*/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
 
        System.out.println();
    }
 
    // Driver method
    public static void main(String args[])
    {        
        int arr[] = {12, 11, 13, 5, 6};
 
        InsertionSort ob = new InsertionSort();        
        ob.sort(arr);
         
        printArray(arr);
    }
}

আউটপুটঃ 5 6 11 12 13

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