Assignment: Searching and Sorting | C++ for EmSAT Achieve PDF Download

Multiple Choice Questions (MCQs)

Q.1. Which of the following is not a sorting algorithm?
(a) Bubble Sort
(b) Binary Search
(c) Insertion Sort
(d) Merge Sort

Ans. (b)

Q.2. Which sorting algorithm has the worst-case time complexity of O(n^2)?
(a) Quick Sort
(b) Merge Sort
(c) Insertion Sort
(d) Selection Sort

Ans. (c)

Q.3. Binary search can be applied to which of the following data structures?
(a) Linked list
(b) Stack
(c) Queue
(d) Array

Ans. (d)

Q.4. Which of the following sorting algorithms is not stable?
(a) Bubble Sort
(b) Quick Sort
(c) Insertion Sort
(d) Merge Sort

Ans. (b)

Q.5. Which search algorithm works on a sorted array and repeatedly divides the search interval in half?
(a) Linear Search
(b) Binary Search
(c) Depth-First Search
(d) Breadth-First Search

Ans. (b)

Higher Order Thinking Skills (HOTS)

Q.1. Consider the following array: [5, 2, 8, 3, 1, 6, 9, 4, 7]. Apply the bubble sort algorithm to sort the array in ascending order. Show the steps involved and provide the sorted array.

Bubble Sort steps:

[5, 2, 8, 3, 1, 6, 9, 4, 7] (Initial array)

[2, 5, 8, 3, 1, 6, 9, 4, 7]

[2, 5, 3, 8, 1, 6, 9, 4, 7]

[2, 5, 3, 1, 8, 6, 9, 4, 7]

[2, 5, 3, 1, 6, 8, 9, 4, 7]

[2, 5, 3, 1, 6, 8, 4, 9, 7]

[2, 5, 3, 1, 6, 8, 4, 7, 9]

[2, 3, 5, 1, 6, 8, 4, 7, 9]

[2, 3, 1, 5, 6, 8, 4, 7, 9]

[2, 3, 1, 5, 6, 8, 4, 7, 9]

[2, 3, 1, 5, 6, 4, 8, 7, 9]

[2, 3, 1, 5, 6, 4, 7, 8, 9]

[2, 1, 3, 5, 6, 4, 7, 8, 9]

[2, 1, 3, 5, 6, 4, 7, 8, 9]

[2, 1, 3, 5, 4, 6, 7, 8, 9]

[2, 1, 3, 5, 4, 6, 7, 8, 9]

[1, 2, 3, 5, 4, 6, 7, 8, 9] (Sorted array)

Q.2. Write a C++ function to perform a binary search on a sorted array. The function should take parameters for the array, the number of elements in the array, and the target element to be searched. If the target element is found, the function should return its index; otherwise, it should return -1.

int binarySearch(int arr[], int size, int target) {

    int low = 0;

    int high = size - 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; // Element not found

}

Q.3. Explain the concept of a stable sorting algorithm. Why is it important in certain applications?

A stable sorting algorithm maintains the relative order of elements with equal values during the sorting process. It means that if two elements have the same value, their order in the sorted array will be the same as their order in the original array. This property is important in certain applications where the original order of equal elements is significant, such as sorting records based on multiple keys or sorting data with associated metadata.

Q.4. Compare and contrast the time complexities of the quick sort and merge sort algorithms. Which algorithm would you prefer for sorting a large array and why?

Quick sort has an average-case time complexity of O(n log n), but its worst-case time complexity is O(n^2) when the pivot selection is poor. Merge sort, on the other hand, has a consistent time complexity of O(n log n) regardless of the input. For sorting a large array, merge sort is generally preferred because of its guaranteed time complexity and stability. However, quick sort can be faster in practice for small arrays or when implemented with optimizations like randomized pivot selection.

Q.5. Describe a scenario where linear search would be a better choice than binary search. Justify your answer.

Linear search would be a better choice than binary search when the array is not sorted. Binary search requires the array to be sorted in ascending order for its effectiveness. Linear search sequentially checks each element of the array until the target element is found or the end of the array is reached. Therefore, if the array is unsorted or the cost of sorting the array is higher than the linear search itself, linear search would be a more suitable option.

Fill in the Blanks

Q.1. The time complexity of bubble sort is _______ in the worst case.

Ans. O(n^2)

Q.2. The _______ algorithm is based on the divide-and-conquer strategy.

Ans. merge sort

Q.3. _______ search is a non-recursive search algorithm that sequentially checks each element of the array.

Ans. Linear

Q.4. The _______ sort algorithm selects the smallest element from the unsorted part of the array and swaps it with the first element.

Ans. selection

Q.5. In the binary search algorithm, the search interval is repeatedly divided in _______.

Ans. half

True or False

Q.1. In quick sort, the pivot element is always the middle element of the array.

Ans. False

Q.2. Bubble sort is an efficient sorting algorithm for large arrays.

Ans. False

Q.3. Binary search can be applied to both sorted and unsorted arrays.

Ans. False

Q.4. Merge sort is an example of an in-place sorting algorithm.

Ans. False

Q.5. Linear search has a worst-case time complexity of O(n).

Ans. True

Hands-On Questions

Q.1. Write a C++ program to implement the selection sort algorithm. The program should take input from the user for the number of elements and the array elements. Display the sorted array as output.

#include <iostream>

using namespace std;

void selectionSort(int arr[], int size) {

    for (int i = 0; i < size - 1; i++) {

        int minIndex = i;

        for (int j = i + 1; j < size; j++) {

            if (arr[j] < arr[minIndex])

                minIndex = j;

        }

        swap(arr[i], arr[minIndex]);

    }

}

int main() {

    int size;

    cout << "Enter the number of elements: ";

    cin >> size;

    int arr[size];

    cout << "Enter the array elements: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    selectionSort(arr, size);

    cout << "Sorted array: ";

    for (int i = 0; i < size; i++)

        cout << arr[i] << " ";

    return 0;

}

Q.2. Implement a C++ program to perform a linear search on an array. The program should take input from the user for the number of elements, the array elements, and the target element to be searched. Display whether the element is found or not.

#include <iostream>

using namespace std;

int linearSearch(int arr[], int size, int target) {

    for (int i = 0; i < size; i++) {

        if (arr[i] == target)

            return i;

    }

    return -1; // Element not found

}

int main() {

    int size;

    cout << "Enter the number of elements: ";

    cin >> size;

    int arr[size];

    cout << "Enter the array elements: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    int target;

    cout << "Enter the target element: ";

    cin >> target;

    int index = linearSearch(arr, size, target);

    if (index != -1)

        cout << "Element found at index " << index << endl;

    else

        cout << "Element not found" << endl;

    return 0;

}

Q.3. Write a C++ program to sort an array using the merge sort algorithm. The program should take input from the user for the number of elements and the array elements. Display the sorted array as output.

#include <iostream>

using namespace std;

void merge(int arr[], int left, int mid, int right) {

    int size1 = mid - left + 1;

    int size2 = right - mid;

    int leftArr[size1];

    int rightArr[size2];

    for (int i = 0; i < size1; i++)

        leftArr[i] = arr[left + i];

    for (int j = 0; j < size2; j++)

        rightArr[j] = arr[mid + 1 + j];

    int i = 0;

    int j = 0;

    int k = left;

    while (i < size1 && j < size2) {

        if (leftArr[i] <= rightArr[j]) {

            arr[k] = leftArr[i];

            i++;

        } else {

            arr[k] = rightArr[j];

            j++;

        }

        k++;

    }

    while (i < size1) {

        arr[k] = leftArr[i];

        i++;

        k++;

    }

    while (j < size2) {

        arr[k] = rightArr[j];

        j++;

        k++;

    }

}

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }

}

int main() {

    int size;

    cout << "Enter the number of elements: ";

    cin >> size;

    int arr[size];

    cout << "Enter the array elements: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";

    for (int i = 0; i < size; i++)

        cout << arr[i] << " ";

    return 0;

}

Q.4. Implement a C++ program to perform a binary search on a sorted array. The program should take input from the user for the number of elements, the array elements, and the target element to be searched. Display whether the element is found or not.

#include <iostream>

using namespace std;

int binarySearch(int arr[], int size, int target) {

    int low = 0;

    int high = size - 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; // Element not found

}

int main() {

    int size;

    cout << "Enter the number of elements: ";

    cin >> size;

    int arr[size];

    cout << "Enter the sorted array elements: ";

    for (int i = 0; i < size; i++)

        cin >> arr[i];

    int target;

    cout << "Enter the target element: ";

    cin >> target;

    int index = binarySearch(arr, size, target);

    if (index != -1)

        cout << "Element found at index " << index << endl;

    else

        cout << "Element not found" << endl;

    return 0;

}

Q.5. Consider the following array: [9, 3, 7, 2, 1, 5, 6, 4, 8]. Apply the insertion sort algorithm to sort the array in ascending order. Show the steps involved and provide the sorted array.

Insertion Sort steps:

[9, 3, 7, 2, 1, 5, 6, 4, 8] (Initial array)

[3, 9, 7, 2, 1, 5, 6, 4, 8]

[3, 7, 9, 2, 1, 5, 6, 4, 8]

[2, 3, 7, 9, 1, 5, 6, 4, 8]

[1, 2, 3, 7, 9, 5, 6, 4, 8]

[1, 2, 3, 5, 7, 9, 6, 4, 8]

[1, 2, 3, 5, 6, 7, 9, 4, 8]

[1, 2, 3, 4, 5, 6, 7, 9, 8]

[1, 2, 3, 4, 5, 6, 7, 8, 9] (Sorted array)