Stack and queue sorting algorithm

1. Define Linear Search.

Linear search (or sequential search) is a
simple searching technique that checks
each element in a list sequentially until the
target element is found or the list ends.
Time Complexity: O(n)
Reference: Weiss, Chapter 2 – Algorithm
Analysis.

2. What is the condition for applying

Binary Search?
Binary search can be applied only on a
sorted array or list. The elements must be
arranged in either ascending or descending
order.
Reference: Weiss, Chapter 3 – Searching
Techniques.

3. What is the worst-case time

complexity of Binary Search?
The worst-case time complexity of binary
search is O(log₂ n) because the search
space is divided by 2 in each iteration.
Reference: Mark Allen Weiss, Section 2.4 –
Binary Search.

4. Write the time complexity of

Insertion Sort in best and worst cases.
 Best case (already sorted list): O(n)
 Worst case (reverse order): O(n²)
Reference: Weiss, Chapter 7 – Sorting
Algorithms.

5. What is the basic idea behind Shell

Sort?
Shell sort improves insertion sort by
allowing the exchange of far-apart elements.
It sorts elements at a specific interval (gap)
and gradually reduces the gap to perform a
final insertion sort.
Reference: Weiss, Section 7.4 – Shellsort.

6. Define pivot in Quick Sort.

A pivot is an element chosen from the array
that divides the list into two sublists —
elements less than the pivot and elements
greater than the pivot.
Reference: Weiss, Section 7.7 – Quicksort.

7. Differentiate between Bubble Sort

and Selection Sort.
Bubble
Feature Selection Sort
Sort
Compares
Selects the
adjacent
smallest/largest
Approach elements
element and places
and swaps
it in correct position
them
No. of
n-1 n-1
Passes
Swaps Many Fewer
Time
Complexi O(n²) O(n²)
ty
Reference: Weiss, Chapter 7 – Sorting.

8. List the advantages of Merge Sort.

1. Stable sort – maintains the relative
order of equal elements.
 2. Predictable O(n log n)
performance in all cases.
3. Well suited for large data sets
and linked lists.
Reference: Weiss, Section 7.6 –
Mergesort.

9. Define Heap Sort.

Heap sort is a comparison-based sorting
algorithm that uses a binary heap data
structure to build a max-heap or min-heap
and repeatedly extract the root to get sorted
output.
Reference: Weiss, Section 7.8 – Heapsort.

10. What is Heapify?

Heapify is the process of arranging nodes in
a binary tree to satisfy the heap property
(parent node is greater or smaller than its
children).
Reference: Weiss, Section 7.8.

11. Define Max-Heap.

A Max-Heap is a binary tree in which the
value of each parent node is greater than
or equal to the values of its children.
Reference: Weiss, 7.8.1.

12. Define Min-Heap.

A Min-Heap is a binary tree where each
parent node is less than or equal to its
children.
Reference: Weiss, 7.8.1.

13. What is Heap Property?

The heap property ensures that every
node’s key value satisfies the heap
condition:
 In a max-heap: parent ≥ children
 In a min-heap: parent ≤ children
Reference: Weiss, 7.8 – Priority
Queues.

14. Write time complexity of Heap Sort

in best and worst case.
 Best Case: O(n log n)
  Worst Case: O(n log n)
Reference: Weiss, Table 7.3 – Sorting
Complexities.

15. Write the time complexity of Quick

Sort in best and worst cases.
 Best Case (balanced partitions): O(n
log n)
 Worst Case (unbalanced partitions):
O(n²)
Reference: Weiss, 7.7 – Quicksort.

16. Write a C program to perform

Linear Search.
#include <stdio.h>
int main() {
int a[10], n, i, key, found = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for(i = 0; i < n; i++) scanf("%d", &a[i]);
printf("Enter key to search: ");
 scanf("%d", &key);
for(i = 0; i < n; i++) {
if(a[i] == key) {
printf("Element found at position
%d", i+1);
found = 1;
break;
}
}
if(!found) printf("Element not found");
return 0;
}
Reference: Weiss, Section 3.1 – Sequential
Search.

17. Explain Binary Search Algorithm

with Sample Input.
Algorithm Steps:
1. Sort the array.
2. Set low = 0, high = n-1.
3. Find mid = (low + high)/2.
 4. If key == a[mid], element found.
5. If key < a[mid], search left half.
6. If key > a[mid], search right half.
7. Repeat until found or low > high.
Example:
Array = [10, 20, 30, 40, 50], key = 30
→ mid = 2 → a[mid] = 30 → Found at
position 3.
Reference: Weiss, Section 3.2 – Binary
Search.

18. Explain Bubble Sort Algorithm with

Time Complexity.
Idea: Repeatedly swap adjacent elements if
they are in wrong order.
Steps:
1. Compare a[j] and a[j+1].
2. Swap if out of order.
3. Repeat for n-1 passes.
Time Complexity:
 Best Case (sorted): O(n)
  Worst Case: O(n²)
Reference: Weiss, 7.3 – Simple Sorts.

19. Describe the Selection Sort

Algorithm with Example.
Idea: Select the smallest (or largest)
element and place it at the correct position.
Example:
Array: [64, 25, 12, 22, 11]
Pass 1 → Smallest = 11 → [11, 25, 12, 22,
64]
Pass 2 → [11, 12, 25, 22, 64]
... Final: [11, 12, 22, 25, 64]
Time Complexity: O(n²)
Reference: Weiss, 7.3.

20. Write and Explain the Insertion Sort

Algorithm.
Idea: Builds sorted list one element at a
time by inserting each new element into its
correct position.
Steps:
1. Start from the second element.
2. Compare with elements before it.
 3. Shift greater elements to the right.
4. Insert the element at the correct
position.
Time Complexity:
 Best: O(n)
 Worst: O(n²)
Reference: Weiss, 7.2.

21. Discuss the Shell Sort Algorithm

with Suitable Example.
Idea: Extension of insertion sort that allows
exchange of far-apart elements.
Steps:
1. Choose a gap sequence (e.g., n/2,
n/4, …, 1).
2. Perform insertion sort for elements
spaced by gap.
3. Reduce gap until it becomes 1.
Example:
Array = [8, 5, 3, 1, 9, 6]
Gap = 3 → Sort elements (8,1), (5,9), (3,6)
Gap = 1 → Perform normal insertion sort.
Time Complexity: Depends on gap
sequence (average O(n^(3/2))).
Reference: Weiss, Section 7.4 – Shellsort.

8 maks

1️⃣ Explain the Quick Sort algorithm

with partition logic and an example.
Definition:
Quick sort is a divide-and-conquer sorting
algorithm developed by Tony Hoare.
It works by selecting a pivot element,
partitioning the array so that all elements
less than the pivot are on one side and
greater elements on the other, and then
recursively sorting the partitions.

Algorithm (as per Weiss, Ch. 7.7):

1. Choose a pivot element from the
array.
2. Partition the array into two parts:
o Left subarray: elements smaller than
pivot.
 o Right subarray: elements greater
than pivot.
3. Recursively apply quick sort to both
subarrays.
4. Combine results to form the sorted
array.

Partition Logic:
int partition(int a[], int low, int high) {
int pivot = a[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (a[j] <= pivot) {
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i+1];
a[i+1] = a[high];
 a[high] = temp;
return (i + 1);
}

Quick Sort Function:

void quicksort(int a[], int low, int high) {
if (low < high) {
int p = partition(a, low, high);
quicksort(a, low, p - 1);
quicksort(a, p + 1, high);
}
}

Example:
Array: [15, 3, 2, 1, 9, 5, 7, 8, 6]
Pivot = 6
→ Left side: [3, 2, 1, 5]
→ Right side: [9, 7, 8, 15]
Recursively sort both halves → Final array:
[1, 2, 3, 5, 6, 7, 8, 9, 15]

Complexity Analysis:
 Time
Case Explanation
Complexity
Best O(n log n) Balanced partition
Averag
O(n log n) Random pivot
e
Pivot is smallest or
Worst O(n²)
largest element
Space Complexity: O(log n) (recursive
stack)
Reference: Weiss, Sec. 7.7 – Quicksort
Algorithm.

2️⃣ Write and explain the Merge Sort

algorithm with recursive breakdown.
Definition:
Merge sort is a divide-and-conquer
algorithm that divides the array into halves,
sorts each half recursively, and then merges
them in a sorted manner.

Algorithm Steps (Weiss, Sec. 7.6):

1. Divide the array into two halves.
2. Recursively sort both halves.
 3. Merge the two sorted halves into
one sorted array.

Pseudocode:
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1
+ j];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j+
+];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

void mergesort(int arr[], int l, int r) {

if (l < r) {
 int m = (l + r) / 2;
mergesort(arr, l, m);
mergesort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

Recursive Breakdown Example:

Array: [10, 80, 30, 90, 40, 50, 70]
Step 1: Divide → [10, 80, 30, 90] and [40,
50, 70]
Step 2: Further divide → [10, 80], [30, 90],
[40, 50], [70]
Step 3: Sort and merge:
→ [10, 80] → [10, 80]
→ [30, 90] → [30, 90]
→ [40, 50, 70] → [40, 50, 70]
→ Merge → [10, 30, 80, 90, 40, 50, 70] →
Final → [10, 30, 40, 50, 70, 80, 90]

Complexity Analysis:
 Time Space
Case
Complexity Complexity
Best O(n log n) O(n)
Averag
O(n log n) O(n)
e
Worst O(n log n) O(n)
Reference: Weiss, 7.6 – Mergesort
Algorithm.

3️⃣ Explain the Heap Sort (Max-Heap)

algorithm with an example.
Definition:
Heap sort uses a binary heap data
structure to sort elements. It first builds a
max-heap, then repeatedly extracts the
largest element (root) and places it at the
end of the array.

Algorithm Steps (Weiss, Sec. 7.8):

1. Build a max-heap from the array.
2. Extract the maximum (root) element
and swap it with the last element.
3. Heapify the reduced heap.
 4. Repeat until all elements are sorted.

C Implementation:
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapsort(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}

Example:
Array: [15, 3, 2, 1, 9, 5, 7, 8, 6]
Step 1: Build max-heap → [15, 9, 7, 8, 3, 5,
2, 1, 6]
Step 2: Swap root (15) with last → [6, 9, 7,
8, 3, 5, 2, 1, 15]
Step 3: Heapify → [9, 8, 7, 6, 3, 5, 2, 1, 15]
Continue until sorted → Final: [1, 2, 3, 5, 6,
7, 8, 9, 15]

Complexity:
 Time
Case
Complexity
Best O(n log n)
Averag
O(n log n)
e
Worst O(n log n)
Space: O(1) (in-place)
Reference: Weiss, Sec. 7.8 – Heapsort.

4️⃣ Write the Heap Sort (Min-Heap)

algorithm with an example.
Definition:
A Min-Heap is a binary heap where each
parent node is smaller than its children.
Heap sort using a min-heap produces the
sorted array in descending order.

Algorithm Steps:
1. Build a min-heap from the array.
2. Swap the root (minimum) with the
last element.
3. Reduce heap size and heapify again.
 4. Repeat until sorted.

C Implementation:
void minHeapify(int arr[], int n, int i) {
int smallest = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < n && arr[left] < arr[smallest])

smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(arr, n, smallest);
}
}
void heapSortMin(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
minHeapify(arr, i, 0);
}
}

Example:
Array: [15, 3, 2, 1, 9, 5, 7, 8, 6]
Step 1: Build min-heap → [1, 3, 2, 6, 9, 5, 7,
8, 15]
Step 2: Swap root (1) with last → [15, 3, 2,
6, 9, 5, 7, 8, 1]
Continue heapifying → Final descending
array: [15, 9, 8, 7, 6, 5, 3, 2, 1]

Complexity:
 Time
Case
Complexity
Best O(n log n)
Averag
O(n log n)
e
Worst O(n log n)
Space: O(1)
Reference: Weiss, Section 7.8 – Heapsort.

✅ Summary Table (for revision):

Time
Algorith Spac Stabili
Type Complexit
m e ty
y
Quick Divide & O(n log n) O(log
No
Sort Conquer avg n)
Merge Divide &
O(n log n) O(n) Yes
Sort Conquer
Heap
Selection O(n log n) O(1) No
Sort
1️⃣ Insertion Sort – Explanation,
Algorithm, and Example
Definition:
Insertion sort is a simple, comparison-based
sorting algorithm that builds the final sorted
array one element at a time. It works similar
to how we sort playing cards in our hands.

Working Principle:
1. Start with the second element (index
1) and assume the first element is
already sorted.
2. Compare the current element with
elements before it.
3. Shift all larger elements one position
to the right.
4. Insert the current element at its
correct position.
5. Repeat for all elements.

Algorithm (Weiss – Section 7.2):

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

Example:
Array: [8, 5, 3, 9, 1]
Pas Ke
Result
s y
[5, 8, 3, 9,
1 5
1]
[3, 5, 8, 9,
2 3
1]
[3, 5, 8, 9,
3 9
1]
[1, 3, 5, 8,
4 1
9]

Time and Space Complexity:

 Tim Spac
Case
e e
Best O(n) O(1)
Averag O(n²
O(1)
e )
O(n²
Worst O(1)
)
Stable: ✅ Yes
Reference: Weiss, Sec. 7.2 – Insertion Sort.

2️⃣ Bubble Sort – Explanation,

Algorithm, and Example
Definition:
Bubble sort repeatedly compares adjacent
elements and swaps them if they are in the
wrong order. It continues until the entire list
is sorted.

Algorithm:
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
 if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}

Example:
Array: [45, 12, 89, 33, 7]
Pas
Result
s
[12, 45, 33, 7,
1
89]
[12, 33, 7, 45,
2
89]
[12, 7, 33, 45,
3
89]
[7, 12, 33, 45,
4
89]

Complexity:
Cas Tim Spac
e e e
Best O(n) O(1)
Wors O(n²
O(1)
t )
Stable: ✅ Yes
Reference: Weiss, Sec. 7.3 – Bubble Sort.

3️⃣ Selection Sort – Explanation,

Algorithm, and Example
Definition:
Selection sort works by selecting the
smallest element from the unsorted portion
of the list and swapping it with the first
unsorted element.

Algorithm:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min])
 min = j;
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

Example:
Array: [64, 25, 12, 22, 11]
Pas
Result
s
[11, 25, 12, 22,
1
64]
[11, 12, 25, 22,
2
64]
[11, 12, 22, 25,
3
64]

Complexity:
Cas Tim Spac
e e e
Best O(n² O(1)
Cas Tim Spac
e e e
)
Wors O(n²
O(1)
t )
Stable: ❌ No
Reference: Weiss, Sec. 7.3 – Selection Sort.

4️⃣ Shell Sort – Explanation, Algorithm,

and Example
Definition:
Shell sort is an optimized version of
insertion sort that allows exchange of
elements that are far apart. It uses a gap
sequence to perform sorting in stages.

Algorithm (Weiss – Section 7.4):

void shellSort(int arr[], int n) {
for (int gap = n/2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
 for (j = i; j >= gap && arr[j-gap] >
temp; j -= gap)
arr[j] = arr[j-gap];
arr[j] = temp;
}
}
}

Example:
Array: [8, 5, 3, 1, 9, 6]
Gap = 3: Compare (8,1), (5,9), (3,6) →
[1,5,3,8,9,6]
Gap = 1: Insertion sort → [1,3,5,6,8,9]

Complexity:
Depends on gap sequence.
Typical gap (n/2, n/4, …, 1): Average O(n¹·⁵)
Stable: ❌ No
Reference: Weiss, Sec. 7.4 – Shell Sort.

5️⃣ Quick Sort – Explanation, Algorithm,

and Example
(See detailed version above — summarized
below)
 Divide and conquer algorithm.
 Choose pivot → partition array →
recursively sort both sides.
Complexities:
Cas
Time Space
e
O(n log O(log
Best
n) n)
Wors O(log
O(n²)
t n)
Stable: ❌ No
Reference: Weiss, Sec. 7.7 – Quicksort.

6️⃣ Merge Sort – Explanation, Algorithm,

and Example
 Splits array recursively, sorts halves,
then merges.
 Always O(n log n) time complexity.
 Needs O(n) extra space.
Stable: ✅ Yes
Reference: Weiss, Sec. 7.6 – Merge Sort.

7️⃣ Heap Sort – Max-Heap Algorithm

Steps:
1. Build a max heap.
2. Swap root with last element.
3. Heapify reduced heap.
4. Repeat until sorted.
Complexity: O(n log n)
Stable: ❌ No
Reference: Weiss, Sec. 7.8.

8️⃣ Heap Sort – Min-Heap Algorithm

Steps:
1. Build a min heap.
2. Swap root with last element.
3. Heapify reduced heap.
4. Produces descending order.
Complexity: O(n log n)
Stable: ❌ No
Reference: Weiss, Sec. 7.8.
📊 Summary Table for Exam Revision
Algori Appro Be Aver Wo Sta Spa
Type
thm ach st age rst ble ce
Inserti Increm O( O(n O(1 Simpl
O(n²) ✅
on ental n) ²) ) e
Bubbl Exchan O( O(n O(1 Simpl
O(n²) ✅
e ge n) ²) ) e
Selecti Selectio O( O(n O(1 Simpl
O(n²) ❌
on n n²) ²) ) e
O(
Gap- n O(n^ O(n O(1 Advan
Shell ❌
based log 1.5) ²) ) ced
n)
O( Divide
Partitio n O(n O(n O(lo -
Quick ❌
n log log n) ²) g n) Conqu
n) er
O( Divide
O(n
n O(n O(n -
Merge Merge log ✅
log log n) ) Conqu
n)
n) er
Heap Heap O( O(n O(n ❌ O(1 Select
Algori Appro Be Aver Wo Sta Spa
Type
thm ach st age rst ble ce
n
log
log log n) ) ion
n)
n)