1- [SB] Consider the following array: {76, 6, 4, 64, 145, 350, 7, 3, 563}. Trace

Question

1-

[SB] Consider the following array: {76, 6, 4, 64, 145, 350, 7, 3, 563}. Trace and demonstrate the steps used to execute the following sorting algorithms on this data (see Chapter 14.4 in the textbook, page W639 for an example of tracing merge sort) :

selection sort

insertion sort

merge sort

2-

[SB] What is the Big-Oh for the following polynomial expressions? (See W635 for how to determine their Big-Oh.)

8n+3n2+6

7n3-2n2+6n

n2+nlogn

50n+0.05n3

3-

Suppose you are trying to look for a word in a dictionary that is organized alphabetically. Would it be more efficient to perform a linear search or a binary search? Explain.

Explanation / Answer

1)

#include <stdio.h>
#include <math.h>

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

// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}

/* Driver program to test insertion sort */
int main()
{
int arr[] = {76, 6, 4, 64, 145, 350, 7, 3, 563};
int n = sizeof(arr)/sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.