Analysis of algorithms viva questions / Interview questions - set1 /sorting algorithms

Top 10 Questions on Sorting Algorithms and Divide and Conquer Approach

Understanding basic sorting algorithms and the divide and conquer approach is crucial for every computer science student. Below are the most frequently asked questions with answers from Module 1: Introduction to Algorithms.

1. What is Selection Sort and how does it work?

Selection Sort is a comparison-based algorithm that divides the array into a sorted and unsorted part. It repeatedly selects the minimum element from the unsorted section and moves it to the beginning.

• Time Complexity: O(n²)
• Stable: No
• In-place: Yes

2. What are the steps involved in Insertion Sort?

Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position among the previously sorted elements.

• Best Case: O(n)
• Worst Case: O(n²)
• Stable: Yes
• In-place: Yes

3. What is the Divide and Conquer approach? Give an example.

The Divide and Conquer strategy breaks a problem into smaller subproblems, solves them recursively, and combines the solutions.

Example: Merge Sort, Quick Sort.

4. How is the minimum and maximum of an array found using Divide and Conquer?

The array is split into halves, and the minimum and maximum are found in each half recursively. These are then compared to get the final result. It reduces the number of comparisons compared to the naive approach.

5. Explain Merge Sort algorithm.

Merge Sort divides the array into halves, recursively sorts them, and merges the sorted halves.

• Time Complexity: O(n log n)
• Stable: Yes
• In-place: No

6. How does Quick Sort work and what is its worst-case scenario?

Quick Sort picks a pivot, partitions the array around it, and recursively sorts the partitions. The worst-case occurs when the smallest or largest element is consistently chosen as pivot.

• Best/Average Case: O(n log n)
• Worst Case: O(n²)

7. What is Binary Search? When can it be used?

Binary Search efficiently finds an element in a sorted array by dividing the search space in half at each step.

• Time Complexity: O(log n)
• Requirement: The array must be sorted

8. Compare Merge Sort and Quick Sort.

Feature	Merge Sort	Quick Sort
Time Complexity	O(n log n)	O(n log n)
Worst Case	O(n log n)	O(n²)
Stability	Stable	Not Stable
Space	Not In-place	In-place

9. What are the advantages of using Insertion Sort over other algorithms?

Insertion Sort is simple, efficient for small datasets, and especially useful when the array is already nearly sorted. It is also a stable and in-place sorting algorithm.

10. In which scenarios is Selection Sort preferred?

Selection Sort is useful when memory writes are costly, as it makes the minimum number of swaps. It is also easy to implement for small data sets.

---

Conclusion: These fundamental algorithm questions form the base for advanced topics in data structures and algorithms. Mastering them will help you excel in technical interviews and academic exams.

Written by Dr. Radhika Nanda | HOD – Computer Engineering