Search This Blog

Insertion Sort

ইনসার্শন সর্ট : ইনসার্শন সর্ট - এ অ্যারেকে ২টি ভাগে ভাগ করা হয়। একটি সর্টেড অংশ এবং অন্যটি আনসার্টেড অংশ। এরপর আনসার্টেড অংশ থেকে প্রতিবার একটি করে ডেটা সর্টেড অংশে ইনসার্ট করা হয়। এজন্যই এই সর্ট কে ইনসার্শন সর্ট বলে।

টাইম কমপ্লেক্সিটি : ওর্স্ট কেসে ইনসার্শন সর্টের টাইম কমপ্লেক্সিটি O(n*n).

কার্যপ্রণালী :  আমরা প্রথমে এই অ্যানিমেশনটা দেখি এবং ইনসার্শন সর্ট বুঝার চেষ্টা করি।

                                      
স্টেপ ১ - এটা যদি প্রথম উপাদান হয়, তাহলে কিছু করার দরকার নেই। এটা এমনিতেই সর্টেড আছে।
স্টেপ ২ - পরবর্ত্তী উপাদানটি সিলেক্ট করি।
স্টেপ ৩ -  এটিকে আগের সকল উপাদান এর সাথে তুলনা করি।
স্টেপ ৪ -  যতক্ষণ এর আগের উপাদান গুলো বড় থাকে ততক্ষন তুলনা করতে থাকি এবং 
স্টেপ ৫ - অবশেষে উপাদানটি ইনসার্ট করি।
স্টেপ ৬ - প্রক্রিয়াটি শেষ পর্যন্ত চালাতে থাকি।


কোডঃ 


insertion_sort(int arr[],int n){ int x,i,j; for(i=1;i<n;i++){ x = arr[i]; j = i-1; while(j>=0 && arr[j]>x){ arr[j+1] = arr[j]; j--; } arr[j+1] = x; } }
 প্রথমেই অ্যালগরিদমটি ইমপ্লিমেন্ট করার জন্য আমরা একটি ফর লুপ নিয়েছি যেন তুলনা করার কাজটি বার বার করা যায়। ফর লুপের কন্ডিশনটি 1 থেকে n-1 পর্যন্ত চলবে। এখানে লক্ষ্য করার বিষয় হলো আমরা লুপ 0 থেকে শুরু না করে 1 থেকে শুরু করেছি । অ্যারে [0] কে আমরা ইনসার্টেড পার্ট হিসাবে ধরেছি । 

পরবর্তী ২ লাইনে আমরা x ও j এর ভ্যালু এসাইন করেছি।
             x = যে ভ্যালু ইনসার্ট করব 
              j = ইনসার্টেড পার্ট এর শেষ ইনডেক্স 

এরপর একটি while লুপ চলবে। 
while লুপের ভিতর কন্ডিশন দিয়েছি arr[j]>x [ যতক্ষণ পর্যন্ত x এর পূর্বের ভ্যালুগুলো বড় থাকবে ততক্ষণ পর্যন্ত রিপ্লেস করতে থাকবো) এবং এটা পূর্বের 0 তম ইনডেক্স পর্যন্ত চলবে তাই j>=0 কন্ডিশন দেওয়া হয়েছে।

এখন এই দুটি কন্ডিশন সত্য হলে অর্থাৎ পূর্বের ভ্যালু (arr[j] এর মান) পরের ভ্যালুর ( arr[i] বা x এর ভ্যালু) চেয়ে বড় হলে আমরা x এর ভ্যালু যে ইনডেক্সে আছে সেই ইনডেক্সে  arr[j] এর মান বসাবো। এরপর যেখানে  x এর ভ্যালু বড় সেখানে while লুপ বন্ধ হয়ে যাবে এবং সেখানেই আমরা x এর মানটি বসিয়ে দিবো। 



No comments

Powered by Blogger.