What is linear search and its time complexity?

Linear search checks each element sequentially. Time complexity: O(1) best, O(n) average/worst. Works on unsorted arrays.

What is binary search and its time complexity?

Binary search divides a sorted array in half repeatedly. Time complexity: O(log n) worst-case, requires sorted input.

What is bubble sort and is it stable?

Bubble sort repeatedly swaps adjacent elements if out of order. Time: O(n²), stable, in-place.

What is selection sort and is it stable?

Selection sort finds minimum and swaps with first unsorted position. Time: O(n²), unstable, in-place.

What is insertion sort and is it stable?

Insertion sort builds sorted portion by inserting elements in correct position. Time: O(n²) worst, O(n) best, stable, in-place.

Sorting and Searching Algorithms in C: Bubble, Selection, Insertion Sort & Linear/Binary Search with Examples

Q: What is sorting stability?

A stable sort preserves relative order of equal elements. Important for multi-key sorting.

Q: Which of bubble, selection, and insertion sort are stable?

Bubble and Insertion are stable. Selection sort is unstable.

Q: What is in-place sorting?

In-place sorting uses O(1) extra space. All three (bubble, selection, insertion) are in-place.

1. What are sorting and searching in DSA?

Sorting arranges elements in a specific order (e.g., ascending or descending), while searching finds the position or existence of an element in a collection. Both are fundamental for efficient data processing in C programs.

2. Why are sorting and searching important?

Sorting organizes data for faster searching, better presentation, or optimized processing. Searching retrieves specific data efficiently, critical for applications like databases or user queries.

3. What are common sorting and searching algorithms in C?

Sorting: Bubble, Selection, Insertion, Merge, Quick Sort.
Searching: Linear Search, Binary Search.

4. What is linear search?

Linear search sequentially checks each element in a collection until the target is found or the end is reached. It works on unsorted data.

5. Can you give an example of linear search in C?

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) { // O(n) time
        if (arr[i] == target) return i; // Return index
    }
    return -1; // Not found
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5, target = 8;
    printf("%d\n", linearSearch(arr, n, target)); // Output: 2
    return 0;
}

6. What is binary search?

Binary search finds a target in a sorted array by repeatedly dividing the search space in half, comparing the middle element to the target.

7. Can you give an example of binary search in C?

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) { // O(log n) time
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // Not found
}

int main() {
    int arr[] = {1, 2, 3, 4, 5}; // Must be sorted
    int n = 5, target = 3;
    printf("%d\n", binarySearch(arr, n, target)); // Output: 2
    return 0;
}

8. What are the time complexities of linear and binary search?

Linear Search:

Best: O(1) (target at start)
Average/Worst: O(n)

Binary Search:

Best: O(1) (target at middle)
Average/Worst: O(log n)

9. What are the advantages and disadvantages of linear and binary search?

Linear Search:

Advantages: Works on unsorted data, simple to implement.
Disadvantages: Inefficient for large datasets (O(n)).

Binary Search:

Advantages: Very efficient for sorted data (O(log n)).
Disadvantages: Requires sorted data, more complex.

10. What is bubble sort?

Bubble sort repeatedly compares adjacent elements and swaps them if out of order, “bubbling” larger elements to the end.

11. Can you give an example of bubble sort in C?

#include <stdio.h>

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

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}

12. What is selection sort?

Selection sort finds the minimum element in the unsorted portion of the array and swaps it with the first unsorted position.

13. Can you give an example of selection sort in C?

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) { // O(n²) time
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}

14. What is insertion sort?

Insertion sort builds a sorted portion by inserting each element into its correct position, shifting others as needed.

15. Can you give an example of insertion sort in C?

#include <stdio.h>

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) { // O(n²) time
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}

16. What are the time complexities of bubble, selection, and insertion sort?

Bubble Sort:

Best: O(n) (already sorted)
Average/Worst: O(n²)

Selection Sort:

Best/Average/Worst: O(n²) (always scans entire unsorted portion)

Insertion Sort:

Best: O(n) (already sorted)
Average/Worst: O(n²)

17. What are the advantages and disadvantages of these sorting algorithms?

Bubble Sort:

Advantages: Simple, stable, in-place.
Disadvantages: Very inefficient (O(n²)).

Selection Sort:

Advantages: In-place, simple, minimal swaps (O(n)).
Disadvantages: Always O(n²), not stable.

Insertion Sort:

Advantages: Stable, in-place, efficient for small or nearly sorted data.
Disadvantages: O(n²) for large datasets.

18. What is sorting stability?

A sorting algorithm is stable if it preserves the relative order of equal elements in the sorted output. Example: If two items with value 5 appear in order A, B, a stable sort keeps A before B.

19. Which of bubble, selection, and insertion sort are stable?

Bubble Sort: Stable (maintains order of equal elements).
Selection Sort: Unstable (swaps may reorder equal elements).
Insertion Sort: Stable (inserts elements without swapping equal ones).

20. Can you demonstrate stability with an example in C?

Example: Sorting objects with equal keys.

#include <stdio.h>

struct Item {
    int value;
    char label;
};

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

int main() {
    struct Item arr[] = {{5, 'A'}, {2, 'B'}, {5, 'C'}}; // Two items with value 5
    int n = 3;
    insertionSort(arr, n); // Stable: Keeps A before C
    for (int i = 0; i < n; i++) {
        printf("(%d, %c) ", arr[i].value, arr[i].label); // Output: (2, B) (5, A) (5, C)
    }
    return 0;
}

21. What is in-place sorting?

In-place sorting modifies the input array directly without requiring additional memory proportional to input size (O(1) extra space, excluding recursion stack).

22. Which of bubble, selection, and insertion sort are in-place?

All three (Bubble, Selection, Insertion) are in-place, using only a constant amount of extra space (e.g., for temp variables during swaps).

23. What are the advantages and disadvantages of in-place sorting?

Advantages: Saves memory, suitable for systems with limited resources.
Disadvantages: May be slower or less stable than non-in-place algorithms (e.g., merge sort).

24. What is the space complexity of these sorting algorithms?

Bubble/Selection/Insertion Sort: O(1) (in-place, only temp variables).

25. How does stability impact sorting applications?

Stability is critical when sorting by multiple keys (e.g., sort by name, then age). Stable algorithms ensure earlier sorts (e.g., by name) are preserved when sorting by a second key (e.g., age).

26. How do you analyze the complexity of sorting and searching algorithms?

Identify basic operations (e.g., comparisons, swaps).
Count operations as a function of input size n.
Use Big O for worst-case, average-case, or best-case.
Consider space usage (in-place vs. extra memory).

27. Can you analyze the complexity of bubble sort?

#include <stdio.h>

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;
            }
        }
    }
}

Time Complexity:

Best: O(n) (already sorted, no swaps).
Average/Worst: O(n²) (nested loops with n iterations each).

Space Complexity: O(1) (in-place, only temp variable).

Analysis: Outer loop runs n-1 times, inner loop runs up to n-i-1 times, total comparisons ≈ n²/2.

28. Can you analyze the complexity of binary search?

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Time Complexity:

Best: O(1) (target at middle).
Average/Worst: O(log n) (search space halves each iteration).

Space Complexity: O(1) (iterative version).

Analysis: Each iteration divides the search space by 2, requiring log₂(n) steps.