Compare performance in terms of time complexity of
Insertion Sort, Bubble Sort & Selection sort
Compare Insertion Sort, Bubble Sort, and Selection Sort based on time
complexity in different scenarios:
Explanation:
• Insertion Sort:
o Best case is O(n) when the array is already sorted.
o Efficient for small or nearly sorted data.
o Performs fewer comparisons/swaps than Bubble Sort in general.
• Bubble Sort:
o Also O(n) in best case (with optimization – early exit if no swaps).
o Performs a lot of unnecessary swaps – usually slower in practice.
• Selection Sort:
o Always O(n²), regardless of input.
o Finds the minimum each time and swaps once per pass – fewest
swaps among the three.
o Not stable, unless specifically modified.
Summary:
• Insertion Sort is generally the most efficient of the three for small or
nearly sorted datasets.
• Bubble Sort is simple but rarely used in practice due to inefficiency.
• Selection Sort is predictable but lacks adaptability and stability.
Given an array apply radix sort. (No need for algorithm).
Write the steps.
Sure! Here's how Radix Sort works step-by-step on an example array. Let's say
we are given this array:
[170, 45, 75, 90, 802, 24, 2, 66]
We will sort the numbers digit by digit starting from the least significant digit
(LSD).
Step-by-step Execution of Radix Sort
Step 1: Sorting by 1s place (units digit)
We group the numbers based on the last digit:
• 0: 170, 90
• 2: 802, 2
• 4: 24
• 5: 45, 75
• 6: 66
Result after 1st pass:
[170, 90, 802, 2, 24, 45, 75, 66]
Step 2: Sorting by 10s place
We group the numbers based on the second-last digit:
• 0: 802, 2
• 2: 24
• 4: 45
• 6: 66
• 7: 170, 75
• 9: 90
Result after 2nd pass:
[802, 2, 24, 45, 66, 170, 75, 90]
Step 3: Sorting by 100s place
We group the numbers based on the third-last digit:
• 0: 2, 24, 45, 66, 75, 90
• 1: 170
• 8: 802
Final Sorted Array:
[2, 24, 45, 66, 75, 90, 170, 802]
Quick Sort & Merge Sort. Write the algorithm. Explain with
example the execution. Analyze (derive) the best, average
and worst time complexity.
Quick sort algorithm :-
QUICKSORT(arr, low, high):
if low < high:
pi = PARTITION(arr, low, high)
QUICKSORT(arr, low, pi - 1)
QUICKSORT(arr, pi + 1, high)
PARTITION(arr, low, high):
pivot = arr[high] (or any other pivot strategy)
i = low - 1
for j = low to high - 1:
if arr[j] <= pivot:
i=i+1
swap arr[i] with arr[j]
swap arr[i+1] with arr[high]
return i + 1 (pivot index)
Example: Sort [10, 7, 8, 9, 1, 5]
Step 1: Initial Call
• low = 0, high = 5
• Pivot = 5
Partition step:
• After partition: [1, 5, 8, 9, 10, 7]
• Pivot 5 is placed at index 1
Step 2: Recurse on Left [1] and Right [8, 9, 10, 7]
• Left: already sorted
• Right: Pivot = 7
After partition: [1, 5, 7, 9, 10, 8] → Pivot 7 at index 2
Continue recursively:
• Partition [9, 10, 8] → Pivot = 8
After: [1, 5, 7, 8, 10, 9] → Pivot 8 at index 3
• Partition [10, 9] → Pivot = 9
Final sorted array: [1, 5, 7, 8, 9, 10]
Time Complexity Analysis
Let’s analyze based on how balanced the pivot divides the array:
1. Best Case (Balanced Split)
Each partition splits array into two equal halves → O(log n) levels
Each level does O(n) work ⇒ Total = O(n log n)
2. Average Case
Random distribution of pivot positions → O(n log n) on average
3. Worst Case (Highly Unbalanced)
Pivot is always smallest/largest (e.g., sorted or reverse-sorted input)
n levels with n-1, n-2, ..., 1 comparisons ⇒ Total = O(n²)
Merge Sort Algorithm:-
MERGE-SORT(arr, left, right):
if left < right:
mid = (left + right) / 2
MERGE-SORT(arr, left, mid)
MERGE-SORT(arr, mid+1, right)
MERGE(arr, left, mid, right)
MERGE(arr, left, mid, right):
create left_sub = arr[left...mid]
create right_sub = arr[mid+1...right]
merge the two subarrays into arr[left...right] in sorted order
Example: Sort [38, 27, 43, 3, 9, 82, 10]
Step 1: Divide
• Split into: [38, 27, 43, 3] and [9, 82, 10]
Split further:
• [38, 27] → [38] and [27]
• [43, 3] → [43] and [3]
• [9, 82, 10] → [9] and [82, 10] → [82] and [10]
Step 2: Conquer (Sort and Merge)
• Merge [38] and [27] → [27, 38]
• Merge [43] and [3] → [3, 43]
• Merge [82] and [10] → [10, 82]
Then:
• Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
• Merge [9] and [10, 82] → [9, 10, 82]
Final merge:
• Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
Time Complexity Analysis
Let’s break down the time complexity of Merge Sort:
1. Divide Step
Each divide splits the array in half → takes O(log n) levels.
2. Merge Step
Each level requires a full pass through the array to merge → O(n) work per
level.
⏱ Total Time = O(n log n)
4-Queen Problem
Write all possible optimum solutions
Total Solutions:
There are 2 unique solutions (if you ignore symmetrical
rotations/reflections),
but 8 total solutions when you count all symmetrical versions.
Here are all 8 valid board configurations where Q represents a queen:
♟ Solution 1
.Q..
...Q
Q...
..Q.
Positions: [1, 3, 0, 2]
♟ Solution 2
..Q.
Q...
...Q
.Q..
Positions: [2, 0, 3, 1]
♟ Solution 3
..Q.
.Q..
...Q
Q...
Positions: [2, 1, 3, 0]
♟ Solution 4
.Q..
...Q
..Q.
Q...
Positions: [1, 3, 2, 0]
♟ Solution 5
Q...
..Q.
.Q..
...Q
Positions: [0, 2, 1, 3]
♟ Solution 6
...Q
.Q..
Q...
..Q.
Positions: [3, 1, 0, 2]
♟ Solution 7
Q...
...Q
.Q..
..Q.
Positions: [0, 3, 1, 2]
♟ Solution 8
..Q.
Q...
...Q
.Q..
Positions: [2, 0, 3, 1] (same as Solution 2 — but possibly rotated)
