Assignment: Sorting | DSA in C++ - Software Development PDF Download

Instructions

This assignment consists of multiple-choice questions (MCQs), high-order thinking questions (HOTS), fill in the blanks, true or false, and hands-on questions.

• Answer all the questions to the best of your knowledge.
• Each question carries one mark.
• There is no negative marking.
• Read the questions carefully before answering.
• At the end of the worksheet, you will find detailed answers to all the questions.

MCQs

1. Which of the following sorting algorithms has a worst-case time complexity of O(n^2)?
(a) Merge Sort
(b) Quick Sort
(c) Bubble Sort
(d) Insertion Sort
Ans. (c)

2. Which sorting algorithm is known for its stability?

(a) Bubble Sort
(b) Selection Sort
(c) Quick Sort
(d) Merge Sort
Ans. (a)

3. In which scenario is Bubble Sort most suitable?
(a) When the list is already sorted
(b) When the list is almost sorted
(c) When the list is in reverse order
(d) When the list contains only unique elements
Ans. (b)

4. The process of repeatedly dividing the input list into smaller sublists until each sublist contains a single element is a characteristic of which sorting algorithm?
(a) Selection Sort
(b) Merge Sort
(c) Quick Sort
(d) Insertion Sort
Ans. (b)

5. Which of the following sorting algorithms is an in-place sorting algorithm?
(a) Merge Sort
(b) Quick Sort
(c) Insertion Sort
(d) Selection Sort
Ans. (b)

HOTS (High-Order Thinking Questions)

Q.1. Explain the working principle of the Selection Sort algorithm. What is its time complexity?

Selection Sort works by repeatedly finding the minimum element from the unsorted part of the list and swapping it with the element at the beginning of the unsorted part. Its time complexity is O(n²).

Q.2. Compare Bubble Sort and Insertion Sort. Discuss their time complexity and suitability for different scenarios.

Bubble Sort and Insertion Sort both have a worst-case time complexity of O(n^2). However, Bubble Sort is suitable for scenarios when the list is almost sorted, as it performs fewer swaps compared to Insertion Sort. On the other hand, Insertion Sort performs better when the list is partially sorted, as it takes advantage of the partially sorted nature of the list.

Q.3. Explain the merge operation in the Merge Sort algorithm. How does it work to merge two sorted sublists?

The merge operation in Merge Sort combines two sorted sublists into a single sorted sublist. It works by comparing the first elements of the two sublists and placing the smaller element in the merged sublist. This process continues until both sublists are completely merged.

Q.4. Describe the Quick Sort algorithm and explain its partitioning process.

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting an element called the pivot and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The partitioning process rearranges the elements in such a way that the pivot element is in its correct sorted position. This process is repeated recursively on the subarrays until the entire array is sorted.

Q.5. Why is Merge Sort often preferred over Quick Sort for sorting large datasets?

Merge Sort is often preferred over Quick Sort for sorting large datasets because it has a guaranteed worst-case time complexity of O(n log n), while Quick Sort's worst-case time complexity is O(n²) in certain scenarios. Merge Sort's time complexity makes it more efficient for large datasets.

Fill in the Blanks

1. The time complexity of Bubble Sort is __________.

The time complexity of Bubble Sort is O(n²).

2. In Insertion Sort, an element is compared and shifted until it finds its ________ position.

In Insertion Sort, an element is compared and shifted until it finds its correct position.

3. Merge Sort is based on the divide-and-__________ strategy.

Merge Sort is based on the divide-and-conquer strategy.

4. Quick Sort uses a __________ element as a pivot for partitioning the array.

Quick Sort uses a pivot element as a pivot for partitioning the array.

5. The worst-case time complexity of Quick Sort is ________.

The worst-case time complexity of Quick Sort is O(n²).

True or False

1. Merge Sort has a time complexity of O(n²).

False

2. Bubble Sort is a stable sorting algorithm.

True

3. Selection Sort always requires the same number of comparisons, regardless of the input order.

True

4. Insertion Sort is an example of an in-place sorting algorithm.

True

5. Quick Sort can be implemented as a recursive algorithm.

True

Hands-On Questions

1. Implement the bubble sort algorithm in C++.

Bubble Sort:

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]) {

                // Swap elements

                int temp = arr[j];

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

                arr[j + 1] = temp;

            }

        }

    }

}

2. Write a function to perform selection sort on an array of integers.

Selection Sort:

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

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

        int minIndex = i;

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

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

                minIndex = j;

            }

        }

        // Swap elements

        int temp = arr[minIndex];

        arr[minIndex] = arr[i];

        arr[i] = temp;

    }

}

3. Implement the insertion sort algorithm in C++.

Insertion Sort:

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;

    }

}

4. Write a recursive function to perform merge sort on an array of integers.

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

    int i = 0, j = 0, k = 0;

    while (i < leftSize && j < rightSize) {

        if (left[i] <= right[j]) {

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

        } else {

            arr[k++] = right[j++];

        }

    }

    while (i < leftSize) {

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

    }

    while (j < rightSize) {

        arr[k++] = right[j++];

    }

}

void mergeSort(int arr[], int n) {

    if (n <= 1) {

        return;

    }

    int mid = n / 2;

    int left[mid];

    int right[n - mid];

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

        left[i] = arr[i];

    }

    for (int i = mid; i < n; i++) {

        right[i - mid] = arr[i];

    }

    mergeSort(left, mid);

    mergeSort(right, n - mid);

    merge(arr, left, mid, right, n - mid);

}

5. Implement the quick sort algorithm in C++.

Quick Sort:

int partition(int arr[], int low, int high) {

    int pivot = arr[high];

    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {

        if (arr[j] < pivot) {

            i++;

            // Swap elements

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

    }

    // Swap elements

    int temp = arr[i + 1];

    arr[i + 1] = arr[high];

    arr[high] = temp;

    return i + 1;

}

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}