Write a version of the sequential search algorithm that can be used to search a

Question

Write a version of the sequential search algorithm that can be used to search a sorted list. Consider the following list: 4, 16, 28, 36, 48, 64, 69, 80, 84, 92, 148, 150 Using a sequential search on ordered lists, which you designed in (a), how many comparisons are required to determine whether the following items are in the list? (Recall that comparisons mean item comparisons, not index comparisons.) 48 70 92 4 Consider the following list: 5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110 Using the binary search as described in this chapter, how many comparisons are required to find whether the following items are in the list? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop. 32 20 105 60 Assume the following list of keys: 90, 12, 2, 80, 55, 11, 17, 15, 58, 98, 36 This list is to be sorted using the insertion sort algorithm as described in this chapter for array-based lists. Show the resulting list after seven passes of the sorting phase - that is. after seven iterations of the for loop. Assume the following list of keys: 36, 55, 8S, 55, 65, 75, 13, 62, 86, 9, 23, 74, 2, 100, 98 This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middle element of the list. Give the resulting list after one call to the function partition. What is the size of the list that the function partition partitioned? What are the sizes of the two sublists created by the function partition? Suppose that L is a list of 11 elements and it is sorted using the merge sort algorithm. What are the sizes of the first and second sublists after the first execution of the function divide? How many times is the function divide called to sort L?. Each of the following expressions represents the number of operations for certain algorithms. What is the order of each of these expressions n^2 + 6n + 4 5N^3 + 2n + 8 (n^2 + 1) (3n + 5) 5(6n + 4) Let L be a sorted list of size 1000. In the worst case, to determine whether an element x is in L, what is the minimum number of comparisons made by a comparison-based search algorithm? Suppose that L is a list of 10,000 elements. Find the average number of comparisons made by bubble sort, selection sort, and insertion sort to sort L.. Let L be a list of 1024 distinct elements. Suppose L is sorted using a comparison-based algorithm. In the worst case, what is the minimum number of key comparisons to sort L? Suppose that L is a list of 10,000 elements. Find the average number of comparisons made by quick sort and merge sort to sort L..

Explanation / Answer

1)sequential search:

#include <iostream>
using namespace std;
int a[]={4,16,28,36,48,64,69,80,84,92,148,150};
int cmp=0;
int sequentialSearch(int key, int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
if(a[i] == key){

return i + 1;
}
else
cmp++;
}
return 0;
}
void sorted(int a[],int n)
{
int i,j,temp;
cout << "do sort : ";
for (i = 1; i <= n; i++)
{
for (j = i; j >= 1; j--)
{
if (a[j] < a[j-1])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
else
break;
}
}
}
int main()
{
int i, key, pos;

cout << "Enter the item to be searched :";
cin >> key;
sorted(a,11);
pos = sequentialSearch(key, a, 12);
if (pos == 0)
cout <<"Search unsuccessful : ";
else
cout <<"key found at position :" << pos << endl;
cout << "number of comparisons for " << key << " are " << cmp+1 <<endl;
return 0;
}

output:

for 48 it took 5 comparisons.

for 70 it took 13 comparisons.

for 92 it took 10 comparisons.

for 48 it took 1 comparisons.

2)

3) insertion sort

#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
int a[16], i, j, k, temp;
cout<<"enter the elements ";
for (i = 0; i < 11; i++)
{
cin>>a[i];
}
for (i = 1; i <= 7; i++)
{
for (j = i; j >= 1; j--)
{
if (a[j] < a[j-1])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
else
break;
}
}
cout<<"sorted array after 7 iterations: "<<endl;
for (k = 0; k < 11; k++)
{
   cout<<a[k]<<" " ;
}
cout << endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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