Question

6. First try to predict how many times will the following for loops execute? What is the output for (i = 17; i>1; i = i/2) for (i = 2; j <i; j = 1 + 3) cout <<j«<i+j << endl; Then create a main program to include this code, compile and run to check your prediction -7. Write a program to show the first two passes in the execution of the Bubble sort on the following ordered set (show how the order changes as the program executes each pas) You may use the code from your textbook and this data: { 20, 32, 50, 48, 19, 10, 5, 8, 12}; 8. Write a program to show the first two passes in the execution of one the Selection( min) sort on the following ordered set (show how the order changes as the program executes each pass) You may use the code from your textbook and this data: { 20, 32, 50, 48, 19, 10, 5, 8, 12); 9. Given the following recursive definition f(1) = f(2)= 2 f(n) = 2 * f(n-1) + f(n - 2) write the C++ code to implement the corresponding program and use it to calculate f(5) and f(15) (You need to write both the main() and the f(n) function.)

Answer 1

Answer 6

i is initialized to 17 and reducing by half each time so first for loop will be running for i = 17, 8, 4, 2,

For i = 17, inner for loop will be running for j = 2, 5, 8, 11, 14 => Total 5 times

For i = 8, inner for loop will be running for j = 2, 5 => Total 3 times

For i = 4, inner for loop will be running for j = 2 => Total 1 times

For i = 2,inner for loop will not run.

So, total time for loops execute = 5 + 2 + 1 = 8 times

Answer 7

#include <iostream> using namespace std; void print(int arr[], int size) { int i; for (i = 0; i < size; i++) cout « arr[i] « " "; cout <« endl; // Bubble sort void bubbleSort(int arr[], int n) { int i, j; // running bubble sort only for 2 passes for (i = 0; i < 2; i++) { for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { arr[j]; arr[j + 1]; arr[j + 1] = temp; int temp arr[j] // After each pass printing the result cout <« "\nBubble Sort After Pass " <« i « ": " print(arr, n); int main() { int arr[] = { 20, 32, 50, 48, 19, 10, 5, 8, 12}; int n = sizeof(arr) / sizeof(arr[0]); cout <« "Initially unsorted array : "; print(arr, n); bubbleSort(arr, n); return 0;

Code

#include <iostream>
using namespace std;

void print(int arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       cout << arr[i] << " ";
   cout << endl;
}

// Bubble sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   // running bubble sort only for 2 passes
   for (i = 0; i < 2; i++)
   {
       for (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;
           }
       }
       // After each pass printing the result
       cout << "\nBubble Sort After Pass " << i << ": ";
       print(arr, n);
   }
}

int main()
{
   int arr[] = { 20, 32, 50, 48, 19, 10, 5, 8, 12};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Initially unsorted array : ";
   print(arr, n);
   bubbleSort(arr, n);
   return 0;
}

Test Output

Initially unsorted array 20 32 50 48 19 10 5 8 12 Bubble Sort After Pass 0: 20 32 48 19 10 5 8 12 50 Bubble Sort After Pass 1: 20 32 19 10 5 8 12 48 50

Answer 8

#include <iostream> using namespace std; void print(int arr[], int size) |{ int i; for (i = 0; i < size; i++) cout <« arr[i] « " "; cout <« endl; [} // Selection sort void selectionSort(int arr[], int n) { int i, j, min; // running selection sort only for 2 passes for (i = 0; i < 2; i++) %3D { min = i; for (j = i + 1; j < n; j++) // Find the minimum element in unsorted array { if (arr[j] < arr[min]) min = j; // Swap the found minimum element with the first element arr[i]; = arr[min]; arr[min] - temp; int temp arr[i] · // After each pass printing the result cout <« "\Selection Sort After Pass " « i « ": "; print(arr, n); [} gint main() int arr[] = { 20, 32, 50, 48, 19, 10, 5, 8, 12}; sizeof(arr) / sizeof(arr[0]); cout <« "Initially unsorted array : "; int n = print(arr, n); selectionSort(arr, n); return 0; [}

Code

#include <iostream>
using namespace std;

void print(int arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       cout << arr[i] << " ";
   cout << endl;
}

// Selection sort
void selectionSort(int arr[], int n)
{
   int i, j, min;
   // running selection sort only for 2 passes
   for (i = 0; i < 2; i++)
   {
       // Find the minimum element in unsorted array
       min = i;
       for (j = i + 1; j < n; j++)
       {
           if (arr[j] < arr[min])
               min = j;
       }
       // Swap the found minimum element with the first element
       int temp = arr[i];
       arr[i] = arr[min];
       arr[min] = temp;

       // After each pass printing the result
       cout << "\Selection Sort After Pass " << i << ": ";
       print(arr, n);
   }
}

int main()
{
   int arr[] = { 20, 32, 50, 48, 19, 10, 5, 8, 12};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Initially unsorted array : ";
   print(arr, n);
   selectionSort(arr, n);
   return 0;
}

Test Output

Initially unsorted array : 20 32 50 48 19 10 5 8 12 5 32 50 48 19 10 20 8 12 5 8 50 48 19 10 20 32 12 Selection Sort After Pass 0: Selection Sort After Pass 1: