Which sorting algorithm below is not comparison-based?
A
Merge sort
B
Heap sort
C
Counting sort
D
Quick sort
উত্তরের বিবরণ
Sorting algorithms মূলত দুই ধরনের হয়—comparison-based এবং non-comparison-based। Comparison-based অ্যালগরিদমগুলো উপাদানগুলোর মধ্যে তুলনা করে (greater than, less than ইত্যাদি) সঠিক ক্রম নির্ধারণ করে, যেখানে non-comparison-based অ্যালগরিদমগুলো তুলনা না করেই বিশেষ পদ্ধতিতে ডেটা সাজায়। প্রদত্ত বিকল্পগুলোর মধ্যে Counting Sort হলো এমন একটি অ্যালগরিদম, যা comparison-based নয়।
Counting Sort (Non-Comparison Sort):
এই অ্যালগরিদমটি সংখ্যাগুলোর মানের ওপর ভিত্তি করে কাজ করে, তুলনার ওপর নয়। এটি ইনপুট ডেটার প্রতিটি মান কতবার এসেছে তা গণনা করে এবং সেই গণনার ওপর ভিত্তি করে উপাদানগুলোকে আউটপুট অ্যারেতে সঠিক অবস্থানে স্থাপন করে। যেহেতু এখানে কোনো উপাদানকে অন্যটির সঙ্গে তুলনা করা হয় না, তাই এটি non-comparison-based sorting পদ্ধতির অন্তর্ভুক্ত।
Counting Sort সাধারণত তখন ব্যবহৃত হয়, যখন:
-
ইনপুট মানগুলো পূর্ণসংখ্যা (integers) হয়।
-
ইনপুটের মানগুলোর range সীমিত (k) থাকে।
-
চাওয়া হয় linear time performance, অর্থাৎ সময় জটিলতা ( O(n + k) )।
কাজের ধাপ সংক্ষেপে:
-
ইনপুট অ্যারের প্রতিটি উপাদানের মান অনুযায়ী একটি count array তৈরি করা হয়।
-
প্রতিটি মান কতবার এসেছে তা গণনা করা হয়।
-
এরপর এই count ব্যবহার করে আউটপুট অ্যারেতে উপাদানগুলোকে তাদের সঠিক অবস্থানে স্থাপন করা হয়।
অন্যদিকে comparison-based sorting অ্যালগরিদমগুলো হলো:
-
Merge Sort: বিভাজন ও তুলনার মাধ্যমে উপাদান সাজায়; সময় জটিলতা ( O(n \log n) )।
-
Heap Sort: হিপ ডেটা স্ট্রাকচারের ওপর নির্ভর করে তুলনা করে উপাদান সাজায়।
-
Quick Sort: উপাদানগুলোকে পিভটের ভিত্তিতে তুলনা করে ভাগ করে সাজায়।
এগুলো সবই উপাদানগুলোর তুলনা ছাড়া কাজ করতে পারে না, তাই এদের বলা হয় comparison-based sorting algorithms।
উপসংহার:
Counting Sort কোনো উপাদানের মধ্যে তুলনা না করে তাদের গণনা ও অবস্থান নির্ধারণের মাধ্যমে সাজায়, তাই এটি একটি non-comparison-based sorting algorithm।
সঠিক উত্তর: গ) Counting Sort
0
Updated: 2 days ago
_______________ algorithm is the most prominent method to avoid deadlock.
Created: 3 days ago
A
Banker's
B
Elevator
C
Karin's
D
None of the above
Banker’s Algorithm হলো একটি deadlock avoidance algorithm, যা operating system-এ রিসোর্স বরাদ্দ নিয়ন্ত্রণে ব্যবহৃত হয়। এটি Edsger Dijkstra উদ্ভাবন করেন। তাই সঠিক উত্তর হলো ক) Banker’s।
কাজের প্রক্রিয়া:
-
Safety Check: কোনো প্রক্রিয়ার রিসোর্স অনুরোধ মঞ্জুর করার আগে সিস্টেম একটি simulation চালিয়ে দেখে যে রিসোর্স বরাদ্দের পর সিস্টেম নিরাপদ (safe) অবস্থায় থাকবে কিনা।
-
Safe State: যদি বরাদ্দের পর এমন একটি safe sequence পাওয়া যায় যেখানে সব প্রক্রিয়া তাদের প্রয়োজনীয় রিসোর্স পেয়ে সফলভাবে সম্পন্ন হতে পারে, তবে সিস্টেম নিরাপদ ধরা হয়।
-
Decision: শুধুমাত্র তখনই অনুরোধটি মঞ্জুর করা হয় যখন সিস্টেম নিরাপদ থাকে; অন্যথায় প্রক্রিয়াটি অপেক্ষায় থাকে যেন deadlock এড়ানো যায়।
-
অতিরিক্ত শর্ত: প্রতিটি প্রক্রিয়াকে execution শুরু করার আগে তার সর্বাধিক প্রয়োজনীয় রিসোর্সের সংখ্যা জানাতে হয়, যাতে অ্যালগরিদম সঠিকভাবে রিসোর্স ব্যবস্থাপনা করতে পারে।
অতএব, Banker’s Algorithm সিস্টেমকে এমন অবস্থায় রাখে যাতে কোনো deadlock সৃষ্টি না হয় এবং রিসোর্স বরাদ্দ সবসময় safe state বজায় রাখে।
0
Updated: 3 days ago
The impedance of a series RLC circuit.
Created: 2 days ago
A
√R2 + (XL + XC)2
B
√R2 + (XL - XC)2
C
R - f(XL + XC)
D
R + f(XL + XC)
একটি series RLC circuit–এ রোধ (R), ইন্ডাকট্যান্স (L), এবং ক্যাপাসিট্যান্স (C) ধারাবাহিকভাবে যুক্ত থাকে। সার্কিটের মোট impedance (Z) হলো এই তিনটি উপাদানের সমন্বিত বিরোধিতা, যা কারেন্ট প্রবাহকে বাধা দেয়।
ব্যাখ্যা:
-
ইন্ডাকটর (L) কারেন্ট পরিবর্তনের বিরোধিতা করে এবং ফ্রিকোয়েন্সি বাড়লে এর রিঅ্যাকট্যান্স বৃদ্ধি পায়।
-
ক্যাপাসিটার (C) ভোল্টেজ পরিবর্তনের বিরোধিতা করে, কিন্তু ফ্রিকোয়েন্সি বাড়লে এর রিঅ্যাকট্যান্স কমে যায়।
-
মোট impedance নির্ভর করে এবং -এর পার্থক্যের ওপর।
0
Updated: 2 days ago
In the worst case, the number of comparisons in the Insertion sort algorithm is:
Created: 3 days ago
A
n(n+1)
B
n log n
C
n(n-1)/2
D
n(n-1)/4
Insertion Sort একটি এমন অ্যালগরিদম যা একবারে একটি করে উপাদান নিয়ে সাজানো অংশে সঠিক স্থানে বসায়। প্রতিটি ধাপে এটি নতুন উপাদানকে সাজানো অংশের উপাদানগুলোর সঙ্গে তুলনা করে সঠিক অবস্থান নির্ধারণ করে। সবচেয়ে খারাপ অবস্থায় বা Worst Case তখন ঘটে, যখন অ্যারে সম্পূর্ণ বিপরীত ক্রমে থাকে।
এই অবস্থায় প্রতিটি নতুন উপাদানকে তার আগের সব উপাদানের সঙ্গে তুলনা করতে হয়। ধাপে ধাপে বিশ্লেষণটি এমন—
-
ইনডেক্স 1–এর উপাদানকে ইনডেক্স 0–এর সঙ্গে তুলনা করতে হয় → 1টি তুলনা
-
ইনডেক্স 2–এর উপাদানকে ইনডেক্স 1 ও 0–এর সঙ্গে তুলনা করতে হয় → 2টি তুলনা
-
ইনডেক্স 3–এর উপাদানকে ইনডেক্স 2, 1, ও 0–এর সঙ্গে তুলনা করতে হয় → 3টি তুলনা
-
এভাবে চলতে থাকে যতক্ষণ না ইনডেক্স n–1–এর উপাদানকে ইনডেক্স n–2 থেকে 0 পর্যন্ত সব উপাদানের সঙ্গে তুলনা করতে হয় → **(n–1)**টি তুলনা
অতএব, মোট তুলনার সংখ্যা হয়:
1 + 2 + 3 + ... + (n–1) = n(n–1)/2
অর্থাৎ Insertion Sort–এর Worst Case Comparisons = n(n–1)/2, যা O(n²) টাইম কমপ্লেক্সিটি নির্দেশ করে।
0
Updated: 3 days ago
