সর্টিং - ১

সর্টিং(sorting)

ভূমিকাঃ

সর্টিং(sorting) হলো একাধিক অবজেক্টকে ক্রমানুক্রমে সাজানো।  দুই ধরনের সর্টিং(sorting) আছে। 

১। ইন্টারনাল সর্টিং(internal sorting)

     যদি অবজেক্ট এর মোট সংখ্যা মেইন মেমোরিতে ফিট করে তবে তা ইন্টারনাল সর্টিং(internal            sorting)

২।এক্সটারনাল সর্টিং(external sorting)

      যদি সর্টিং এর সময় অবজেক্ট এর মোট  সংখ্যা এত বড় হয় যে তা এক্সটারনাল স্টোরেজে রাখা            লাগে তবে তা এক্সটারনাল সর্টিং(external sorting) 

 ইন্টারনাল সর্টিং(internal sorting) এর কিছু উদাহরন

O(n) অ্যালগরিদমস(algorithms)

1. বাকেট সর্ট(Bucket Sort)

           unsorted=  {3,11,2,9,1,5,5} 

          

           প্রক্রিয়াঃ

১।   আনসর্টেড(unsorted)  অবজেক্টগুলোর মধ্যে থেকে সর্বোচ্চ ভ্যালুর মানের সমান সংখ্যক ইনডেক্স বিশিষ্ট নাল array ডিক্লেয়ার করতে হবে। ইনডেক্সগুলোতে কাউন্টার থাকবে যার মান প্রাথমিকভাবে শূন্য রাখতে হয়। এই সমস্যা দূরীকরনের জন্য লিংকড লিস্ট ব্যবহার করা হয়।

Index	0	1	2	3	4	5	6	7	8	9	10	11
counter	0	0	0	0	0	0	0	0	0	0	0	0

২।   তারপর ইনপুট array এর ভ্যালুগুলোকে তার মানের সমান সংখ্যাক ইনডেক্সে একটি কাউন্টারকে বাড়াতে হবে। যেমনঃ 3 যাবে তিন নম্বর ইনডেক্সে, 11 যাবে ১১ নম্বর ইনডেক্সে।  ডুপ্লিকেট নাম্বারের সমস্যা দূরীকরনের জন্য এই কাউন্টার ব্যাভার করা হয়।

Index	0	1	2	3	4	5	6	7	8	9	10	11
counter	0	1	1	1	0	2	0	0	0	1	0	1

   sorted = {1,2,3,5,5,9,11}

O(n²) অ্যালগরিদমস(algorithms)

১।বাবল সর্ট(Bubble Sort)

        unsorted = {7, 5, 2, 4, 3, 9}

 প্রক্রিয়াঃ

সবচেয়ে বড় মানের অবজেক্টটি বাবলের মত উপরে উঠে যাবে। মানে, একটি অবজেক্ট তার পরবর্তী অবজেক্টের সাথে তুলনা করবে ও অবস্থান পরিবর্তন (swapping) করবে প্রয়োজন অনুসারে।

1st step


7,5,2,4,3,9
5,7,2,4,3,9
5,2,7,4,3,9
5,2,4,7,3,9
5,2,4,3,7,9

2nd step

5,2,4,3,7,9
2,5,4,3,7,9
2,4,5,3,7,9
2,4,3,5,7,9


3rd step

2,4,3,5,7,9
2,3,4,5,7,9

sorted ={2,3,4,5,7,9}


worst case runtime: O(n²) Explanation :-

২। সিলেকশন সর্ট(Selection Sort)
  unsorted ={29, 64, 73, 34, 20}

 প্রক্রিয়াঃ

১। array দুটি অংশে বিভক্ত। sorted এবং unsorted । প্রাথমিকভাবে পুরা array unsorted থাকে।

Sorted data	Unsorted data
	64	25	12	22	11

২। সিলেকশনঃ সর্বনিম্ন অবজেক্টটিকে সিলেক্ট করতে হবে অবশিস্ট unsorted array থেকে।

Sorted data	Unsorted data
	64	25	12	22	11

৩।সোয়াপিংঃ সিলেক্টেড অবজেক্টটিকে স্টারটিং পজিশনে আনতে হবে।

Sorted data	Unsorted data
	11	25	12	22	64

৪।কাউন্টার শিফটঃ unsorted array এর কাউন্টার এক ডিক্রিমেন্ট হবে।

Sorted data	Unsorted data
11	25	12	22	64

sorted={11,12,22,25,64}


worst case runtime: O(n²) Explanation :-

২। ইনসার্টেশন সর্ট(Insertion Sort)
  unsorted ={29, 64, 73, 34, 20}


 প্রক্রিয়াঃ

১। array দুটি অংশে বিভক্ত। sorted এবং unsorted । প্রাথমিকভাবে পুরা array unsorted থাকে। 

Sorted data	Unsorted data
	64	25	12	22	11

২।যেহেতু শুণ্য ইনডেক্সের আগে কোন অবজেক্ট নাই তাই সেটি প্রাথমিকভাবে Sorted data তে যাবে।

Sorted data	Unsorted data
64	25	12	22	11

৩। unsorted ডাটাগুলোর প্রথম ইনডেক্সটি sorted ডাটা গুলোর সাথে তুলনা করে সোয়াপিং করতে হবে।

Sorted data	Unsorted data
25	64	12	22	11

Sorted data		Unsorted data
25	64	12	22	11

এভাবে,

sorted={11,12,22,25,64}

worst case runtime: O(n²) Explanation :-











O(n log n) অ্যালগরিদমস(algorithms)

১।মার্জ সর্ট (Mergesort)

unsorted= {27  10  12  25  34  16  15  31

}

 প্রক্রিয়াঃ


১। পুরো  array কে সমান দুইভাগে ভাগ করতে হবে যতক্ষন না পর্যন্ত element গুলো এক  array তে একটি করে থাকে।

              27  10  12  25  34  16  15  31

     Divide it into two parts

       27  10  12  25                      34  16  15  31

divide each part into two parts

  27 10         12 25                 34 16               15 31

divide each part into two parts

 27   10       12    25             34     16           15      31

২।প্রতিটা subarray কে merge ও sort একইসাথে করতে করতে একটি array তে আনতে হবে।

merge (sorting also) parts


10  27            12  25                         16  34            15  31

merge (sorting also) parts

   10  12  25  27                     15  16  31  34

merge parts (sorting also) into one

            10  12  15  16  25  27  31  34