সন্নিবেশ বাছাই সময় জটিলতা

Sannibesa Bacha I Samaya Jatilata



নিম্নলিখিত সংখ্যা বিবেচনা করুন:

50 60 30 10 80 70 20 40







যদি এই তালিকাটি ক্রমবর্ধমান ক্রমে সাজানো হয়, তাহলে তা হবে:



10 20 30 40 50 60 70 80



যদি এটিকে নিচের ক্রমে সাজানো হয়, তাহলে তা হবে:





80 70 60 50 40 30 20 10

সন্নিবেশ বাছাই হল একটি সাজানোর অ্যালগরিদম যা তালিকাকে আরোহী ক্রমে বা অবরোহ ক্রমে সাজাতে ব্যবহৃত হয়। এই নিবন্ধটি শুধুমাত্র ক্রমবর্ধমান ক্রম অনুসারে সাজানোর বিষয়ে আলোচনা করে। এই নথিতে প্রদত্ত একই যুক্তি অনুসরণ করে অবরোহী ক্রমে সাজানো। এই নিবন্ধের উদ্দেশ্য সন্নিবেশ বাছাই ব্যাখ্যা করা হয়. সি-তে নিম্নলিখিত উদাহরণে প্রোগ্রামিং করা হয়েছে। এখানে একটি অ্যারে ব্যবহার করে সন্নিবেশ বাছাই ব্যাখ্যা করা হয়েছে।



সন্নিবেশ সাজানোর জন্য অ্যালগরিদম

একটি সাজানো তালিকা দেওয়া হয়. লক্ষ্য হল একই তালিকা ব্যবহার করে তালিকাটিকে আরোহী ক্রমে সাজানো। একই অ্যারে ব্যবহার করে একটি সাজানো না করা অ্যারে সাজানোকে বলা হয় ইন-প্লেসে সাজানো। এখানে শূন্য ভিত্তিক সূচী ব্যবহার করা হয়েছে। নিম্নরূপ পদক্ষেপ:

    • তালিকাটি শুরু থেকে স্ক্যান করা হয়।
    • স্ক্যানিং চলাকালীন, এর পূর্বসূরির চেয়ে কম যেকোন সংখ্যাটি তার পূর্বসূরীর সাথে অদলবদল করা হয়।
    • এই অদলবদল তালিকা বরাবর চলতে থাকে, যতক্ষণ না এটি অদলবদল করা সম্ভব হয় না।
    • স্ক্যানিং শেষ হলে, বাছাই সম্পূর্ণ হয়।

সন্নিবেশ বাছাই চিত্রণ

সময় জটিলতা মোকাবেলা করার সময়, এটি সবচেয়ে খারাপ ক্ষেত্রে যা সাধারণত বিবেচনা করা হয়। আগের তালিকার জন্য সবচেয়ে খারাপ ব্যবস্থা হল:

80 70 60 50 40 30 20 10

শূন্য থেকে 7 পর্যন্ত সূচক সহ আটটি উপাদান রয়েছে।

সূচক শূন্য এ, স্ক্যানিং 80 এ যায়। এটি একটি আন্দোলন। এই একটি আন্দোলন একটি অপারেশন. এখন পর্যন্ত মোট একটি অপারেশন হয়েছে (একটি আন্দোলন, কোন তুলনা নেই এবং কোন অদলবদল)। ফলাফল হলো:

| 80 70 60 50 40 30 20 10

প্রথম সূচকে, 70-এ একটি আন্দোলন রয়েছে। 70-এর সাথে 80-এর তুলনা করা হয়। 70 এবং 80-এর অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। একটি তুলনা এছাড়াও একটি অপারেশন. এক অদলবদলও এক অপারেশন। এই বিভাগে তিনটি অপারেশন উপলব্ধ করা হয়. এখন পর্যন্ত মোট চারটি অপারেশন হয়েছে (1 + 3 = 4)। নিম্নরূপ ফলাফল:

70 | 80 60 50 40 30 20 10

দুই সূচকে, 60-এ একটি মুভমেন্ট আছে। 60 কে 80 এর সাথে তুলনা করা হয়, তারপর 60 এবং 80 অদলবদল করা হয়। 60 কে 70 এর সাথে তুলনা করা হয়, তারপর 60 এবং 70 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। দুটি তুলনা হল দুটি অপারেশন। দুটি অদলবদল দুটি অপারেশন। এই বিভাগে পাঁচটি অপারেশন উপলব্ধ করা হয়. এখন পর্যন্ত মোট নয়টি অপারেশন হয়েছে (4 + 5 = 9)। নিম্নরূপ ফলাফল:

60 70 | 80 50 40 30 20 10

ইনডেক্স থ্রিতে, 50-এ একটি মুভমেন্ট আছে। 50 কে 80 এর সাথে তুলনা করা হয়, তারপর 50 এবং 80 অদলবদল করা হয়। 50 কে 70 এর সাথে তুলনা করা হয়, তারপর 50 এবং 70 অদলবদল করা হয়। 50 কে 60 এর সাথে তুলনা করা হয়, তারপর 50 এবং 60 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। তিনটি তুলনা তিনটি অপারেশন। তিনটি অদলবদল তিনটি অপারেশন। এই বিভাগটি সাতটি অপারেশন প্রদান করে। এখন পর্যন্ত মোট ষোলটি অপারেশন হয়েছে (9 + 7 = 16)। নিম্নরূপ ফলাফল:

50 60 70 | 80 40 30 20 10

ইনডেক্স চারে, 40-এ একটি মুভমেন্ট আছে। 40 কে 80 এর সাথে তুলনা করা হয়, তারপর 40 এবং 80 অদলবদল করা হয়। 40 কে 70 এর সাথে তুলনা করা হয়, তারপর 40 এবং 70 অদলবদল করা হয়। 40 কে 60 এর সাথে তুলনা করা হয়, তারপর 40 এবং 60 অদলবদল করা হয়। 40 কে 50 এর সাথে তুলনা করা হয়, তারপর 40 এবং 50 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। চারটি তুলনা হল চারটি অপারেশন। চার অদলবদল হল চারটি অপারেশন। এই বিভাগে নয়টি অপারেশন প্রদান করে। এখন পর্যন্ত মোট পঁচিশটি অপারেশন হয়েছে (16 + 9 = 25)। নিম্নরূপ ফলাফল:

40 50 60 70 80 | 30 20 10

ইনডেক্স ফাইভে, 30-এ একটি মুভমেন্ট আছে। 30 কে 80 এর সাথে তুলনা করা হয়, তারপর 30 এবং 80 অদলবদল করা হয়। 30 কে 70 এর সাথে তুলনা করা হয়, তারপর 30 এবং 70 অদলবদল করা হয়। 30 কে 60 এর সাথে তুলনা করা হয়, তারপর 30 এবং 60 অদলবদল করা হয়। 30 কে 50 এর সাথে তুলনা করা হয়, তারপর 30 এবং 50 অদলবদল করা হয়। 30 কে 40 এর সাথে তুলনা করা হয়, তারপর 30 এবং 40 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। পাঁচটি তুলনা হল পাঁচটি অপারেশন। পাঁচটি অদলবদল হল পাঁচটি অপারেশন। এই বিভাগটি এগারোটি অপারেশন প্রদান করে। এখন পর্যন্ত মোট ছত্রিশটি অপারেশন হয়েছে (25 + 11 = 36)। নিম্নরূপ ফলাফল:

30 40 50 60 70 80 | 20 10

সূচী ছয়ে, 20-এ একটি মুভমেন্ট আছে। 20 কে 80 এর সাথে তুলনা করা হয়, তারপর 20 এবং 80 অদলবদল করা হয়। 20 কে 70 এর সাথে তুলনা করা হয়, তারপর 20 এবং 70 অদলবদল করা হয়। 20 কে 60 এর সাথে তুলনা করা হয়, তারপর 20 এবং 60 অদলবদল করা হয়। 20 কে 50 এর সাথে তুলনা করা হয়, তারপর 20 এবং 50 অদলবদল করা হয়। 20 কে 40 এর সাথে তুলনা করা হয়, তারপর 20 এবং 40 অদলবদল করা হয়। 20 কে 30 এর সাথে তুলনা করা হয়, তারপর 20 এবং 30 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। ছয় তুলনা ছয় অপারেশন. ছয়টি অদলবদল হল ছয়টি অপারেশন। এই বিভাগটি তেরোটি অপারেশন প্রদান করে। এখন পর্যন্ত মোট উনচল্লিশটি অপারেশন হয়েছে (36 + 13 = 49)। নিম্নরূপ ফলাফল:

20 30 40 50 60 70 80 | 10

সাত সূচকে, 10-এ একটি নড়াচড়া রয়েছে। 10-এর সাথে 80-এর তুলনা করা হয়, তারপর 10 এবং 80-এর অদলবদল করা হয়। 10 কে 70 এর সাথে তুলনা করা হয়, তারপর 10 এবং 70 অদলবদল করা হয়। 10 কে 60 এর সাথে তুলনা করা হয়, তারপর 10 এবং 60 অদলবদল করা হয়। 10 কে 50 এর সাথে তুলনা করা হয়, তারপর 10 এবং 50 অদলবদল করা হয়। 10 কে 30 এর সাথে তুলনা করা হয়, তারপর 10 এবং 40 অদলবদল করা হয়। 10 কে 30 এর সাথে তুলনা করা হয়, তারপর 10 এবং 30 অদলবদল করা হয়। 10 কে 20 এর সাথে তুলনা করা হয়, তারপর 10 এবং 20 অদলবদল করা হয়। এক আন্দোলন এক অপারেশন। সাতটি তুলনা সাতটি অপারেশন। সাত অদলবদল হল সাতটি অপারেশন। এই বিভাগটি পনেরটি অপারেশন প্রদান করে। এখন পর্যন্ত মোট চৌষট্টিটি অপারেশন হয়েছে (49 + 15 = 64)। নিম্নরূপ ফলাফল:

10 20 30 40 50 60 70 80 10 |

কাজ শেষ! ৬৪টি অপারেশন জড়িত ছিল।

64 = 8 x 8 = 8 দুই

সন্নিবেশ সাজানোর জন্য সময় জটিলতা

সন্নিবেশ সাজানোর সাথে সাজানোর জন্য n উপাদান থাকলে, সম্ভাব্য ক্রিয়াকলাপগুলির সর্বাধিক সংখ্যা n2 হবে, যেমনটি পূর্বে প্রদর্শিত হয়েছে। সন্নিবেশ সাজানোর সময় জটিলতা হল:

চালু দুই )

এটি বিগ-ও স্বরলিপি ব্যবহার করে। বিগ-ও স্বরলিপি বড় হাতের অক্ষরে O দিয়ে শুরু হয়, তারপরে বন্ধনী থাকে। বন্ধনীর ভিতরে সর্বাধিক সম্ভাব্য সংখ্যক অপারেশনের জন্য অভিব্যক্তি রয়েছে।

সি-তে কোডিং

স্ক্যানের একেবারে শুরুতে, প্রথম উপাদানটি তার অবস্থান পরিবর্তন করতে পারে না। প্রোগ্রামটি মূলত নিম্নলিখিত:

# অন্তর্ভুক্ত করুন

অকার্যকর সন্নিবেশ সাজানো ( int এ [ ] , int N ) {
জন্য ( int i = 0 ; i < এন; i++ ) {
int j = i;
যখন ( [ j ] < [ জে- 1 ] && জে- 1 > = 0 ) {
int temp = A [ j ] ; ক [ j ] = ক [ জে- 1 ] ; ক [ জে- 1 ] = temp; // অদলবদল
j--;
}
}
}


insertionSort() ফাংশন সংজ্ঞা বর্ণনা অনুযায়ী অ্যালগরিদম ব্যবহার করে। যখন-লুপের শর্তগুলি নোট করুন। এই প্রোগ্রামের জন্য একটি উপযুক্ত C প্রধান ফাংশন হল:

int প্রধান ( int argc, char ** argv )
{
int n = 8 ;
int এ [ ] = { পঞ্চাশ , 60 , 30 , 10 , 80 , 70 , বিশ , 40 } ;

সন্নিবেশ বাছাই ( একটি ) ;

জন্য ( int i = 0 ; i < n; i++ ) {
printf ( '%i' , এ [ i ] ) ;
}
printf ( ' \n ' ) ;

ফিরে 0 ;
}

উপসংহার

সন্নিবেশ বাছাইয়ের সময় জটিলতা এইভাবে দেওয়া হয়েছে:

চালু দুই )

পাঠক হয়ত একটি খারাপ-কেস সময়ের জটিলতা, গড়-কেস সময়ের জটিলতা এবং সেরা-কেস সময়ের জটিলতার কথা শুনেছেন। সন্নিবেশ সাজানোর সময় জটিলতার এই বৈচিত্রগুলি আমাদের ওয়েবসাইটের পরবর্তী নিবন্ধে আলোচনা করা হয়েছে।