Data Structure and Algorithm . Part : 02

#handyprogrammer

#c++

#c

{ গত পর্বে কথা বলেছিলাম Data Structure কি ? Data Structure কেনো প্রয়োজন ? Common কিছু Data Structure নিয়ে । ঐ পর্বেটা যদি পড়ে না থাকেন তাহলে পড়ে আসার অনুরোধ রইলো ।

কারন, ঐ পর্বে আমি Data Structure কে একদম সহজ ভাবে উপস্থাপনা করেছি । যেন যে কেউ বুজতে পারে বাস্তব জীবনে এবং প্রোগ্রামিং লাইফে Data Structure এর গুরুত্ব কতুটুকু । }

আজকে আমাদের জানার বিষয় হলো Sorting Algorithm নিয়ে । কোন কোন বিষয় জানবো এক নজরে দেখেনি ।

১ - Sorting কি ? এটা খায় নাকি মাথায় দেয় ? ২- Sorting Algorithm কত প্রকার ? ৩ - Bubble Sort .

=====> ১ - Sorting কি ? <========

আসফাক আর শফিক দুই ভাই ।

আসফাক বড় আর শফিক ছোট । আসফাক CSE পড়ালেখা চুকিয়ে দেশের সনাম ধন্য একটি সফটওয়্যার ইন্ডাস্ট্রিতে চাকরি করে । আর, শফিক এবছর CSE তে ভর্তি হয়েছে ।

কোরবানীর ছুটিতে দুই ভাই পরিবারসহ গ্রামে বেড়াতে আসে । আসফাক আর শফিক গ্রামে এসে বিকালে গুরুর হাটে যায় । সেখানে গিয়ে আসফাকের ছোটবেলার বন্ধু নাবিলের সাথে দেখা হয় ।

নাবিল একজন খামারী । নাবিলের খামারে বা আতালে ছোট বড় ১০০ টি গরু আছে । নাবিল খুব অনুরোধ করে আসফাককে বললো " তুই কালকে আমার খামারে আসবী । "

আসফাক তার বন্ধু নাবিলের কথা ফেলতে পরলো না। পরদিন সকালে দুইভাই নাবিলের খামারে যায় ।

আসফাক নাবিলের খামারে গিয়ে দেখে খুবি পরিস্কার এবং গোছানো । আসফাকের সব থেকে যেটা নজর কেড়েছে তা হলো গরুর সাজানোর বিষয় টাকে ।

নাবিল প্রতিটি গরুকে একটি নম্বরওয়ালা বেল্ট পড়িয়েছে । ছোট থেকে বড় গরু গুলোকে ১ থেকে ১০০ পর্যন্ত ক্রমোনুসারে সাজিয়েছে । যেনো, সহজেই গরু গুলোকে খুজে পাওয়া যায় ।

এই সাজানো বিষয়টাকে দেখে আসফাক তার ছোটভাইকে বলতে শুরু করলো :- তুই যেহেতু CSE তে সবে মাত্র ভর্তি হয়েছো তোদের একটি সেমিস্টারে Data Structure and Algorithm শিখাবে ।

সেখানে Sorting Algorithm নামে একটি Algorithm আছে আর এই Sorting Algorithm এর কাজ হচ্ছে । নাবিলের খামারের মতন গুরু গুলোকে সাজিয়ে রাখা ।

মানি, একটি Array এর Element গুলোকে সাজিয়ে রাখা । আর, এই সাজানোকে দুই ভাবে করা যায় ।

১- ছোট থেকে বড় । এটাকে বলে : - Ascending Order . যেমন : ১ ২ ৩ ৪ ৫ ২- বড় থেকে ছোট। এটাকে বলে : - descending Order . যেমন : ৫ ৪ ৩ ২ ১

তুই নাবিলের গরু সাজানোকে বলতে পারাস Ascending আকারে সাজিয়েছে । তাই তোকে যদি কেউ বলে Sorting Algorithm কি ? তুই বলে দিবে: নাবিল ভাইয়ের গুরু সাজানো হচ্ছে Sorting Algorithm.

=====>২- Sorting Algorithm কত প্রকার ?<=====

আসফাক তার ভাইকে বললো । শোন Sorting Algorithm অনেক গুলো আছে । তার মধ্য কিছু Sorting Algorithm এর নাম তোকে বলি ।

1- Bubble Sort. 2- Insertion Sort 3- Selection Sort. 4- Quick Sort. 5- Heap Sort . 6- Counting Sort. 7- Bucket Sort. 8- Tree Sort.

আর হ্যা রাতে তোর সাথে Bubble Sort নিয়ে কথা বলবো ।

=====> ৩ - Bubble Sort . <=====

রাতে, আসফাক শফিককে বলতে শুরু করলো । আচ্ছা শফিক একুরিয়াম দেখছো না ? একুরিয়ামের ভিতরে মাছকে কিন্তু গ্যাস দেওয়া হয়। ঐ গ্যাস গুলো নিচ থেকে পানির উপরে উঠে বুব্দুদ করতে করতে । এই বুব্দুদ কে তুই বলতে পারস ইংলিশে : Bubble .

দেখবি একটি বুব্দুদ পানির নিচ থেকে উঠতে উঠতে যখন একদম উপরে উঠে যায় তখন কিন্তু বুব্দুদ শেষ হয়ে যায় । আর এখানেই আছে Bubble Sort এর ধারনা ।

কিভাবে আছে ? এটা একটি কমন প্রশ্ন । চল বোঝার চেষ্টা করি ।

ধর, আমাদের কাছে একটি Array আছে এর Element সংখ্যা হলো নিচের মতন ।

98 88 58 28 38

আমরা এখন এই Array এর Element এর উপর Bubble Sort করবো।

Bubble Sort এর কাজটা কি ? এটা আগে একটু বোঝার চেষ্টা কর । => Bubble Sort এর কাজ হলো কোন Sorting আকারের Array এর Element কে Ascending বা descending আকারে সাজানো ।

Ascending এবং descending কি মনে আছে ?

এখন চল Array এর Element এর মধ্য ।

এই যে 98 দেখতোছো এটা তুই সেই একুরিয়ামের নিচের বুব্দুদ ধরতে পারো। এখন 98 যা করবে প্রথম ও দেখবে ওর পাশের index এর Element যদি ওর থেকে ছোট হয় তা হলে দুজনকে swap করবে। মানি যায়গা অদলবদল করবে । Befored Bubble Sort -- 98 88 58 28 38 After Bubble Sort -- 88 98 58 28 38

98 ঠিক এই রকম করতে থাকবে ঠিক ঐ পর্যন্ত যতক্ষন পর্যন্ত ও একদম শেষে না যেতে পারছে । ঠিক সেই একুরিয়ামের বুব্দুদ উপরে উঠে শেষ হয়ে যায় ঠিক তেমনি । নিচের সংখ্যা গুলো দেখে বোজার চেষ্টা কর ।

Before Bubble Sort -- 98 88 58 28 38 After Bubble Sort -- 88 98 58 28 38 88 58 98 28 38 88 58 28 98 38 88 58 25 38 98

দেখছো 98 কিন্তু একদম নিচ থেকে উপরে উঠে গিয়েছে । এভাবে লুপ চালিয়ে Array এর Element এর প্রতিটি index এর উপর নিতে হবে । আয় Bubble Sort এর কোডটা যে রকম হবে তোরে দেখাই ।

for(int i=0; i<size; i++)
{
    for(int j=0;  j<size-1; j++)
    {
        if(array[j]>array[j+1])
        {
            int temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
        }
    }
}

এই কোডের মধ্য কি হতে আছে । না হতে আছে কিছু বুঝো নাই ? বোঝার চেষ্টা কর । চিন্তুা করার চেষ্টা কর । প্রোগ্রামিং জিনিসটাই হচ্ছে চিন্তুা করার । যত চিন্তুা করতে পারবি প্রোগ্রামিং নিয়ে, প্রোগ্রামিং শিখতে ততো মজা পাবি ।

যদি মুখস্ত করতে যাস তাহলে আইটকাওয়ালা বাঁশ খাবি ।

আজকে এই পর্যন্তই দেখে হবে অন্য কোন আর্টিকেলে । ভালো লাগলে শেয়ার,লাইক, কমেন্ট করতে ভুলবেন না ।