Quick Sort একটি দক্ষ divide and conquer ভিত্তিক সোর্টিং অ্যালগরিদম, যা বড় আকারের ডেটাসেট দ্রুত সাজানোর জন্য ব্যাপকভাবে ব্যবহৃত হয়। এটি ইন-প্লেস (in-place) পদ্ধতিতে কাজ করে, ফলে অতিরিক্ত মেমরির প্রয়োজন হয় না।

মূল তথ্যসমূহ:

• Divide: একটি pivot element নির্বাচন করে অ্যারেটিকে দুই ভাগে ভাগ করা হয়—এক ভাগে pivot-এর চেয়ে ছোট উপাদানগুলো, আরেক ভাগে বড় উপাদানগুলো রাখা হয়।

• Conquer: এই দুইটি সাবঅ্যারেতে পুনরাবৃত্তি করে (recursively) একই প্রক্রিয়া প্রয়োগ করা হয়।

• Combine: দুটি সাবঅ্যারে সাজানো হয়ে গেলে, সেগুলো একত্রে সঠিক ক্রমে সংযুক্ত হয়; যেহেতু সাজানো কাজ ইন-প্লেস হয়, তাই এই ধাপটি তুলনামূলক সহজ।

• দক্ষতা: গড় অবস্থায় এর সময় জটিলতা O(n log n), যা একে Insertion, Bubble, ও Selection Sort থেকে অনেক দ্রুত করে তোলে।

ভুল বিকল্পসমূহ:

• ক) Insertion Sort: ধাপে ধাপে নতুন উপাদান যোগ করে সাজায়; divide and conquer নয়।

• গ) Bubble Sort: পরপর উপাদানগুলো অদলবদল করে সাজায়; কোনো ভাগ করা হয় না।

• ঘ) Selection Sort: প্রতিবার সবচেয়ে ছোট উপাদান নির্বাচন করে সাজায়; এটি-ও divide and conquer নয়।

অতএব, Quick Sort-ই একমাত্র অ্যালগরিদম যা divide and conquer কৌশল ব্যবহার করে সাজানোর কাজ সম্পন্ন করে।

Answer: গ) Semantic analysis

Explanation:

A compiler works in several phases:

Lexical analysis →→Converts source code into tokens (keywords, identifiers, operators)

Syntax analysis →→   Builds parse tree and checks grammar rules (structure of code)

Semantic analysis →→ Checks meaning of code:

 Example:
int a;
float b;
a = b; // Semantic analysis may warn about type mismatch

Syntax analysis: Correct (assignment statement follows grammar)

Semantic analysis: Detects type mismatch → performs data type checking

Recursion হলো এমন একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেকে নিজেই কল করে। প্রতিটি কলের সময় প্রোগ্রামকে সেই কল সম্পর্কিত তথ্য—যেমন লোকাল ভেরিয়েবল, রিটার্ন অ্যাড্রেস, ও প্যারামিটার—সংরক্ষণ করতে হয় যাতে ফাংশন সম্পূর্ণ হলে ঠিক জায়গায় ফিরে আসতে পারে।

মূল তথ্যসমূহ:

• Stack ব্যবহারের কারণ: এই তথ্যগুলো সংরক্ষণের জন্য ব্যবহৃত হয় একটি Call Stack, যা একটি LIFO (Last In, First Out) কাঠামো অনুসরণ করে।

• কাজের প্রক্রিয়া:

  • Function Call: প্রতিটি কলের সময় একটি stack frame তৈরি হয়ে stack-এর উপরে push হয়।

  • Recursive Calls: প্রতিটি নতুন recursive কলের জন্য নতুন ফ্রেম push হয়।

  • Return: যখন ফাংশন শেষ হয়, তখন সংশ্লিষ্ট ফ্রেমটি stack থেকে pop হয়ে প্রোগ্রাম পূর্বাবস্থায় ফিরে আসে।

• এই প্রক্রিয়াই recursion-কে সঠিকভাবে কার্যকর ও ট্র্যাকযোগ্য করে তোলে।

ভুল বিকল্পসমূহ:

• ক) Linked List: ডেটা সংরক্ষণে ব্যবহৃত হয়, কিন্তু recursion-এর স্বাভাবিক কাঠামো নয়।

• গ) Queue: এটি FIFO (First In, First Out) ক্রমে কাজ করে, যেখানে recursion-এর জন্য LIFO প্রয়োজন।

• ঘ) Array: ডেটা সংরক্ষণে পারে, কিন্তু এটি ডাইনামিক ফাংশন কল স্ট্রাকচার পরিচালনা করতে সক্ষম নয়।

অতএব, recursion পরিচালনায় stack ব্যবহৃত হয়, যা প্রতিটি ফাংশন কলের ট্র্যাক রাখে এবং সঠিক ক্রমে এক্সিকিউশন নিশ্চিত করে।