Write a program that demonstrates different O notations. O(1) - adding a value t
ID: 3688460 • Letter: W
Question
Write a program that demonstrates different O notations. O(1) - adding a value to a partially filled static array O(n) - searching an array for a specific value O(n^2) - bubble sort O(log n) - binary search O(n log n) - quick sort In your program, set up arrays of size 100, 1000, 5000, and 10000, filled with random values. Have a separate function for each of the O notations being tested. In each function, have a counter that keeps track of the number of operations needed to complete the task of the function. An operation is any statement or process that requires the computer to make a decision or execute a statement or declaring a variable. For example, int counter = 0; counter++; if (a == b) //1 operation { a++; //1 operation counter++; } counter = 0; counter++; for(int a=0; a < 5; a++) { counter++; cout << "Hi"; //17 operations counter++; } BE SURE you don't send a sorted array into the O(n log n) function!
Explanation / Answer
#include<iostream.h>
#include<conio.h>
template<class T>
void printarray(T *array,int n)
{
cout<<array[0];
for(int i=1;i<n;i++)
{
cout<<","<<array[i];
}
}
template<class T>
void bubbesort(T *array, int n)//perform bubblesort
{
for(int i=1;i<n;i++)
{
for(int j=1;j<=n;j++)
{
if(array[j-1]>array[j])
{
T temporary=array[j-1];
array[j-1]=array[j];
array[j]=temporary;
} }
} }
void quicksort(T *array,int first,int last) //perform quicksort
{
int i,j,pivot;
if(first<last)
{
pivot=array[first];
i=first;
j=last;
while(i<j)
{
while(array[i]<=pivot&&i<last)
i++;
while(array[j]>=pivot&&j>first)
j--;
if(i<j)
swap(array,i,j);
}
swap(a,first,j);
quicksort(array,first,j-1);
quicksort(array,j+1,last);
}
}
template<class T>
void swap(T *array,int i,int j)
{
T temporary1=array[i];
array[i]=array[j];
array[j]=temporary;
T binarysearch(T array[20],T n,T z)
{
int l,r,mid;
l=0;
r=n-1;
while(l<=r)
{
mid=(l+r)/2;
if(z==array[mid])
return mid;
else
if(z<array[mid])
r=mid-1;
else
l=mid+1;
}
return -1;
}
void main()
{int z,p,t;
int array[]={11,17,15,13,18,14,43,61,10,99};
clrscr();
cout<<" This is the array before sorting";
print(array,10);
bubblesort(array,10); // calling bubblesort
cout<<" This is the array after sorting ";
print(array,10);
quicksort(array,0,10-1); //calling quicksort
cout<<" After Sorting ";
print(array,10);
cout<<" Enter the element to find : ";
cin>>z;
q=binarysearch(array,n,z);
if(q!=-1)
cout<<" The element is found at "<<q+1<<" position";
else
cout<<" Element Not Found!!";
system("pause");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.