Insertion sort

Insertion sort algorithm pseudo code

for i = 1 to length(A) – 1

x = A[i]

j = i

while j > 0 and A[j-1] > x

A[j] = A[j-1]

j = j – 1

A[j] = x

end while

end for

এটা হল insertion sort pseudo code

এখন দেখাযাক ইন্সারসন সরট কিভাবে কাজ করে

১। insertion sort এর ক্ষেত্রে প্রথম নাম্বারটাকে sorted ধরা হয় ।

২। পরে ২ নাম্বার element(অর্থাৎ ডানপাশের element) এর সাথে ১ নাম্বার element(অর্থাৎ বামপাশের element) তুলনা করা হয় যে; ২ নাম্বার element ১ নাম্বার element এর ছেয়ে ছোট কিনা

যদি ছোট হয় তাহলে পরিবর্তন করা।

৩। পরে বামপাশের element গুলুকে sorted ধরা হয় এবং ডানপাশেরটার সাথে তুলনা করাহয় এবং ২ নং রিপিট করা হয় ।

 

 

এখন একটা উদাহারন দেখাযাক

 

বর্ণনা

এখানে ৬ টি unsorted number আছে প্রথম element হিসাবে আছে ৫ যাকে আমরা sorted ধরে নিই

এখন প্রথম element এর সাথে ২ element তলনা করব যে প্রথমটা বড় কিনা ? এখানে যেহেতু প্রথম নাম্বার বড় তাই পরিবর্তন করতে হবে

পরিবর্তন করার পর ২ ৫ ৪ ৬ ১ ৩

এবার ২ এবং ৫ কে sorted ধরা হয় এবং পরে আগের মত ডানপাশের টার সাথে তুলনা করতে হবে

৫ এর ডানপাশের element ৪

এখন তুলনা করব যে বামপাশের element ৫ ; ডানপাশের element ৪ এর ছেয়ে বড় কিনা

যেহেতু ৪<৫

তাই পরিবর্তন করতেহবে

এবার তুলনা করতেহবে ২ এবং ৪ এর মধ্যে

এখানে যেহেতু ২<৪ (মপাশের element ডানপাশের element এর ছেয়ে ছোট)

তাই যেমন আছে তেমন ই থাকবে

এবং পরিবর্তন করার পর ২ ৪ ৫ ৬ ১ ৩

একই ভাবে পরবর্তীতে

৫<৬ সত্য তাই যেমন আছে তেমন ই থাকবে

৬<১ মিথ্যা তাই পরিবর্তন করতে হবে

পরিবর্তন করার পর ২ ৪ ৫ ১ ৬ ৩

এখন ১ কে বামপাশের প্রত্যেকটা element এর সাথে তুলনা করতে হবে যতক্ষণ ১ এর proper place না পাউয়া যাবে

৫<১ মিথ্যা তাই পরিবর্তন করতে হবে

২ ৪ ১ ৫ ৬ ৩

৪<১ মিথ্যা তাই পরিবর্তন করতে হবে

২ ১ ৪ ৫ ৬ ৩

২<১ মিথ্যা তাই পরিবর্তন করতে হবে

১ ২ ৪ ৫ ৬ ৩

এখন লুপ শেষ হবে

এখন ও পুরুপুরি sorted হয়নি

আবার লুপ চালাতে হবে

এখন sorted number গুলুর মধ্যে সবছেয়ে ডানে আছে ৬ তাই ; ৬ কে লাস্ট element ৩ এর সাথে তুলনা করা হয়

৬< ৩ মিথ্যা তাই পরিবর্তন করতে হবে

১ ২ ৪ ৫ ৩ ৬

এখন পূর্বের মত লুপ চালাতে হবে যতক্ষণ ৩ proper place এ না যাবে

৫<৩ মিথ্যা তাই পরিবর্তন করতে হবে

১ ২ ৪ ৩ ৫ ৬

৪<৩ মিথ্যা তাই পরিবর্তন করতে হবে

১ ২ ৩ ৪ ৫ ৬

২<৩ সত্য তাই এখানে লুপ শেষ হবে

এবং ১ ২ ৩ ৪ ৫ ৬ ই হল sorted array

এখন c program implementation দেখাযাক

#include<stdio.h>

int main()

{

int i,j,s,temp,a[20];

printf(“Enter the number of element\n”);

scanf(“%d”,&s);

printf(“Enter %d elemnts\n”,s);

for(i=0;i<s;i++)

scanf(“%d,”,&a[i]);

for(i=1;i<s;i++)

{

temp=a[i];

j=i-1;

while((temp<a[j])&&(j>=0))

{

a[j+1]=a[j];

j=j-1;

}

 

a[j+1]=temp;

 

}

 

 

printf(“After sorting\n”);

for(i=0;i<s;i++)

printf(“%d”,a[i]);

}

এখানে insertion sort শুরু হয়েছে

For লুপ থেকে

Temp variable এর মধ্যে ডানপাশের element কে রাখা হয়েছে

এবং while loop এর মাধ্যমে দেখা হচ্ছে যে ডানপাশের element বামপাশের এলেমেন্ত থেকে ছোট কিনা

ছোট হলে লুপ এর মধ্যে প্রবেশ করবে

এবং

a[j+1]=a[j] মানে

value swap এখানে যেহেতু j=i-1 =0

j এর ভেলু ০ তাই

a[j+1] অর্থাৎ ২য় array index এ প্রথম index এর মান বসবে

আমাদের উদাহারন এর ক্ষেত্রে এটা হবে

৫ , ২ এর জায়গায় বসবে । কারন এখানে ৫ প্রথম element and ২ এর ছেয়ে ছোট

এভাবে প্রত্যেকটা element while loop এ চেক হবে।

 

Bubble sort

 

Bubble sort algorithm হল

for i = 1 to n (last element )
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j]=a[j-1]

১। unsorted  প্রথম number থেকে এক এক করে শেষ নাম্বার পর্যন্ত নাম্বার গুলু তুলনা করা।

২। যদি প্রথম নাম্বার ২য় নাম্বার থেকে বড় হয় (ascending এর ক্ষেত্রে ) তাহলে পরিবর্তন করা ।

এবার একটা উদাহারন দেখা যাক

 

এই পিকচার এ দেখান হয়েছে কিভাবে Bubble sort algorithm কাজ করে ।

বর্ণনা:

এখানে উদাহারন সরুপ  ২ ৩ ৪ ৫ ১ আইরকম একটা unsorted array দেউয়া হয়েছে

যখন প্রথম ২টা নাম্বার এর মধ্যে তুলনা করা হচ্ছে দেখা যাচ্ছে যে ২ , ৩ (২<৩) এর ছেয়ে ছোট তার মানে তারা ঠিক ঠিক অবস্থানে ই আছে তাই লিখা হয়েছে ok .

আবার ২য় ৩য় নাম্বার এর  তলনার ক্ষেত্রে ও একি অর্থাৎ ৩, ৪   এর ছেয়ে ছোট(৩<৪) তার মানে তারা ঠিক ঠিক অবস্থানে ই আছে তাই লিখা হয়েছে ok .

এভাবে পরেরটাও একি অর্থাৎ ৪,৫   এর ছেয়ে ছোট(৪<৫) তার মানে তারা ঠিক ঠিক অবস্থানে ই আছে তাই লিখা হয়েছে ok .

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

অবস্থান পরিবর্তন করার পর ২ ৩ ৪ ১ ৫ । আরকম একটা লিস্ট  পেলাম কিন্ত এটা কি sorted হয়েছে ? হয়নি তাই আবার ও compare করতে হবে

2nd step : আবার ২<৩,৩<৪  ok লিখা হল আগের মত করে । আবার বিপত্তি বাধল ৪,১ এর comparison এ কারন ৪<১ এটা ত ঠিক না ।তাই অবস্থান আবার পরিবর্তন ।

২য় বার অবস্থান পরিবর্তন এর পর

২,৩,১,৪,৫

3rd:এভাবে  ৩<১ পেয়ে অবস্থান আবার পরিবর্তন ২,১,৩,৪,৫

4th :আবার ২<১ পেয়ে অবস্থান পরিবর্তন

১,২,৩,৪,৫

এবং এটা হল আমাদের আসল sorted array or data .

এবার কোড implementation দেখা যাক
#include <stdio.h>

int main()
{
int array[100], n, c, d, swap;

printf(“Enter number of elements\n”);
//কত গুলু নাম্বার নিয়ে কাজ করতেচান যেমন ৫ টা ৬ টা ইত্যাদি
scanf(“%d”, &n);

printf(“Enter %d integers\n”, n);
//উপরে যে নাম্বার ইনপুট দিয়েছেন সেই সংখ্যক, সংখ্যা ইনপুট দিন

for (c = 0; c < n; c++)
scanf(“%d”, &array[c]);

for (c = 0 ; c < ( n – 1 ); c++)
{
for (d = 0 ; d < n – c – 1; d++)
{
if (array[d] > array[d+1])

//এখানে তুলনা করা হচ্ছে যে প্রথম element টা ২য় element এর ছেয়ে বড় কিনা

//যদি বড় হয়

{
swap = array[d];  //প্রথম মানটা কে swap variable  এর মধ্যে রাখেবে
array[d] = array[d+1]; //২য় মানটাকে প্রথমটার মধ্যে রাখবে
array[d+1] = swap;// এবার swap এর মধ্যে রাখা প্রথম মানকে ২য় টায় রাখবে
}
}
}
বিঃদ্রঃ d<n-c-1; লিখার কারন হল যখন আমরা  element  কে সরত করে ফেললাম তখন লাস্ত পর্যন্ত ত আর জাওউয়ার  দরকার নাই

যেমন ২ ৩ ৪ ১ ৫ এখানে ৫ শেষ  অবস্থানে চলে এসেছে তাই এখন আর লাস্ত পর্যন্ত compare করার দরকার নাই

তখন কেবল ৪ টা element  কে compare করলে ই হবে .

এভাবে ৩য় বার ৩ টা  element  কে compare করলে ই হবে

এভাবে ৪রথ বার ২ টা  element  কে compare করলে ই হবে

লুপ একবার  ঘুরবে c এর মান বারতে থাকবে  এবং n-c-1 এর মান ও কমতে থাকবে আর তত কম সংখ্যক element   থাকবে compare করার জন্য