Question

Data Structures and Algorithms CMPS 2720

PLEASE ANSWER CLEARLY

10. Suppose a dataset has N items. On average, how many comparisons and how many saves (not swaps) are needed to sort the dataset using the bubble sort?

11. Suppose a dataset has N items. On average, how many comparisons and how many saves (not swaps) are needed to sort the dataset using the select sort?

12. Suppose a dataset has N items. On average, how many comparisons and how many saves (not swaps) are needed to sort the dataset using the insertion sort?

13. Suppose that an array contains the eight number listed below. How many saves (not swaps) are needed to perform the first pass of the bubble sort? 18 20 12 14 10 16 32 26

14. Suppose that an array contains the eight number listed below. How many saves are needed to perform the first pass of the select sort? 18 20 12 14 10 16 32 26

5. What effect, if any, does the consideration of duplicates in an array have in searching for all records with a specific key?

Answer 1

ANSWERS:

10) Suppose for n-elements, the bubble-sort algo is written as :

// A function to implement bubble sort

void bubbleSort(int arr[], int n)

{

    int i, j;

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

    // Last i elements are already in place

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

        if (arr[j] > arr[j+1])

            swap(&arr[j], &arr[j+1]);

}

So, comparison happens in every loop. Please find the illustration of bubble-sort of 8 elements:

So, for n-elements, the total number of comparisons will be: (n-1)*(n-2)/2

Total number of saves can be equal to number of comparisons if the array is already sorted. So, in that case, no swap will happen.

11) Please find below algo for selection sort. The best part is, it first finds the smallest element, and then swaps with the i^th index.

void selectionSort(int arr[], int n)

{

    int i, j, min_idx;

    // One by one move boundary of unsorted subarray

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

    {

        // Find the minimum element in unsorted array

        min_idx = i;

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

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

            min_idx = j;

        // Swap the found minimum element with the first element

        swap(&arr[min_idx], &arr[i]);

    }

}

So, for n-elements, the total number of comparisons will be: (n-1)*(n-2)/2

And, number of swaps will be equal to N only.

12) Please find below algo for insertion sort:

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)

{

    int i, key, j;

    for (i = 1; i < n; i++)

    {

        key = arr[i];

        j = i - 1;

        /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */

        while (j >= 0 && arr[j] > key)

        {

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

            j = j - 1;

        }

        arr[j + 1] = key;

    }

}

So, for n-elements, the total number of comparisons will be: (n-1)*(n-2)/2

And, number of swaps will be maximum equal to N only.

13) Suppose the elements to be sorted by bubble-sort are:

18 20 12 14 10 16 32 26

So, in 1st pass:

18 20 12 14 10 16 32 26 -> 18 20 12 14 10 16 32 26 (18 and 20 are compared and no swap is performed as 18<20)

18 20 12 14 10 16 32 26 -> 18 12 20 14 10 16 32 26 (20 and 12 are compared and swap is performed)

18 12 20 14 10 16 32 26 -> 18 12 14 20 10 16 32 26  (20 and 14 are compared and swap is performed)

18 12 14 20 10 16 32 26 -> 18 12 14 10 20 16 32 26 (20 and 10 are compared and swap is performed)

18 12 14 10 20 16 32 26 -> 18 12 14 10 16 20 32 26 (20 and 16 are compared and swap is performed)

18 12 14 10 16 20 32 26 -> 18 12 14 10 16 20 32 26 (20 and 32 are compared and no swap is performed as 20<32)

18 12 14 10 16 20 32 26 -> 18 12 14 10 16 20 26 32 (32 and 26 are compared and swap is performed)

Hence, total number of saves in the first pass of this bubble sort is 2.

14) In the selection sort of given array,

18 20 12 14 10 16 32 26
In the first pass, the minimum element is discovered from the remaining array, and swapped with 0th element.

So, after first pass the array will look like:

18 20 12 14 10 16 32 26 ->  10 20 12 14 18 16 32 26

So, single swap happened in first pass and no save happened.

15) To search all records with specific key, duplicates needs to be considered as duplicate values of given key increases the resultant count that needs to be returned. If the array is already sorted, then duplicates make it even easier to find the first occurrence and last occurrence of the specified key and find the total elements that exists. So, duplicates should always be considered while searching foe a key.

PS. I hope the answers are complete and upto the expectations. Please comment if anything else is required in the answer.