C++-এ ইনসার্শন সর্ট টাইম কমপ্লেক্সিটি প্রশ্ন

ইনসার্শন সর্টের টাইম কমপ্লেক্সিটি কত?

টাইম কমপ্লেক্সিটি হল একটি কোড সেট বা অ্যালগরিদমকে প্রসেস বা রান করার জন্য প্রয়োজনীয় সময় যা ইনপুটের পরিমাণের ফাংশন হিসেবে প্রকাশ করা হয়।

ইনসার্শন সর্টের জন্য, 베스트 কেস সিনারিওতে টাইম কমপ্লেক্সিটি O(n) অর্থাৎ big O of n। এবং গড় বা ওৰ্স্ট কেস সিনারিওতে কমপ্লেক্সিটি O(n²)।

নিচের ফর্মের n সাইজ অ্যারে সর্ট করার সময় ইনসার্শন সর্ট অ্যাপ্লাই করলে টাইম কমপ্লেক্সিটি কত হবে: 6, 5, 8, 7, 10, 9 ... i, i-1

উপরের অ্যারে সর্ট করার টাইম কমপ্লেক্সিটি O(n)। এই অ্যালগরিদমটি চাকচকে দেখলে, সব জোড়া তাদের মূল পজিশন থেকে সোয়াপ করা আছে। অর্থাৎ উপাদান ১ এবং ২-এর পজিশন ইন্টারচেঞ্জ, ৩ এবং ৪ ইন্টারচেঞ্জ ইত্যাদি। তাই সর্ট করার সময় অ্যালগরিদমটি শুধু এক অপারেশন n বার নেবে এই অ্যালগরিদম সর্ট করার জন্য।

ইনসার্শন সর্ট ডিফাইন করুন এবং ইনসার্শন সর্টের কোড লিখুন?

ইনসার্শন সর্ট হল একটি সর্টিং অ্যালগরিদম যা ডেটা স্ট্রাকচারকে সর্ট করে উপাদানটিকে সর্ট করা অ্যারেতে তার সঠিক পজিশনে রাখায়।

নিচের কোডটি ইনসার্শন সর্টের ফাংশন দেখাচ্ছে:

উদাহরণ কোড

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int element = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > element) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = element;
    }
}