1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
scoray [572]
3 years ago
7

g Write a program to sort an array of 100,000 random elements using quicksort as follows: Sort the arrays using pivot as the mid

dle element of the array Sort the arrays using pivot as the median of the first, last, and middle elements of the array Sort the arrays using pivot as the middle element of the array. However,, when the size of any sub-list reduces to less than 20, sort the sub-list using insertion sort. Sort the array using pivot as the median of the first, last and middle elements of the array. When the size of any sub-list reduces to less than 20, sort the sub-list using insertion sort. Calculate and display the CPU time for each of the preceding four steps.
Computers and Technology
1 answer:
shtirl [24]3 years ago
7 0

Answer:

header.h->function bodies and header files.

#include<iostream>

#include<cstdlib>

#include<ctime>

using namespace std;

/* Partitioning the array on the basis of piv value. */

int Partition(int a[], int bot, int top,string opt)

{

int piv, ind=bot, i, swp;

/*Finding the piv value according to string opt*/

if(opt=="Type1 sort" || opt=="Type3 sort")

{

piv=(top+bot)/2;

}

else if(opt=="Type2 sort" || opt=="Type4 sort")

{

piv=(top+bot)/2;

if((a[top]>=a[piv] && a[top]<=a[bot]) || (a[top]>=a[bot] && a[top]<=a[piv]))

piv=top;

else if((a[bot]>=a[piv] && a[bot]<=a[top]) || (a[bot]>=a[top] && a[bot]<=a[piv]))

piv=bot;

}

swp=a[piv];

a[piv]=a[top];

a[top]=swp;

piv=top;

/*Getting ind of the piv.*/

for(i=bot; i < top; i++)

{

if(a[i] < a[piv])

{

swp=a[i];

a[i]=a[ind];

a[ind]=swp;

ind++;

}

}

swp=a[piv];

a[piv]=a[ind];

a[ind]=swp;

return ind;

}

void QuickSort(int a[], int bot, int top, string opt)

{

int pindex;

if((opt=="Type3 sort" || opt=="Type4 sort") && top-bot<19)

{

/*then insertion sort*/

int swp,ind;

for(int i=bot+1;i<=top;i++){

swp=a[i];

ind=i;

for(int j=i-1;j>=bot;j--){

if(swp<a[j]){

a[j+1]=a[j];

ind=j;

}

else

break;

}

a[ind]=swp;

}

}

else if(bot < top)

{

/* Partitioning the array*/

pindex =Partition(a, bot, top,opt);

/* Recursively implementing QuickSort.*/

QuickSort(a, bot, pindex-1,opt);

QuickSort(a, pindex+1, top,opt);

}

return ;

}

main.cpp->main driver file

#include "header.h"

int main()

{

int n=100000, i;

/*creating randomized array of 100000 numbers between 0 and 100001*/

int arr[n];

int b[n];

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

arr[i]=(rand() % 100000) + 1;

clock_t t1,t2;

t1=clock();

QuickSort(arr, 0, n-1,"Type1 sort");

t2=clock();

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

arr[i]=b[i];

cout<<"Quick sort time, with pivot middle element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );

cout<<"\n";

t1=clock();

QuickSort(arr, 0, n-1,"Type2 sort");

t2=clock();

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

arr[i]=b[i];

cout<<"Quick sort time, with pivot median element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );

cout<<"\n";

t1=clock();

QuickSort(arr, 0, n-1,"Type3 sort");

t2=clock();

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

arr[i]=b[i];

cout<<"Quick sort time and insertion sort time, with pivot middle element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );

cout<<"\n";

t1=clock();

QuickSort(arr, 0, n-1,"Type4 sort");

t2=clock();

cout<<"Quick sort time and insertion sort time, with pivot median element:"<<(t2 - t1)*1000/ ( CLOCKS_PER_SEC );

return 0;

}

Explanation:

Change the value of n in the main file for different array size. Output is in the same format as mentioned, time is shown in milliseconds.

You might be interested in
The source ip address is 164.109.28.3 subnet mask of 255.255.128.0 network address is
Sergeu [11.5K]
164.109.0.0/17




-------------------------------------------
6 0
2 years ago
The picture has the question on it
Bingel [31]

The answer is B. Row

4 0
2 years ago
Suppose I define some structure type ( studentInfo), then I declare an instance of it and I decide to also create a pointer to t
Nookie1986 [14]

Answer:

a. (p*Main).age = 20;

Explanation:

Pointers use ->

where as normal variable use . to access its members

pMain is the pointer.

*pMain is the value inside pMain.

pMain->age = 20;

This statement equals to

(*pMain).age = 20;

Answer is option a.

8 0
3 years ago
How do you insert text into a presentation?
ElenaW [278]

Answer:

Its most likely the last one

Explanation:

But like, what kind of quesiton is this?

7 0
2 years ago
Read 2 more answers
an ssl client has determined that the certificate authority (ca) issuing a server's certificate is on its list of trusted cas. w
TEA [102]

The next step in verifying the server's identity is:

  • The CA's public key need to validate the CA's digital signature found on the server certificate.

<h3>What is SSL client?</h3>

Secure Sockets Layer (SSL) is known to be a kind of PKI protocol that helps to  authenticate a user's identity and it is one that often encrypt the communication that takes place between the client and the server.

Note that  in the above, the next step in verifying the server's identity is:

  • The CA's public key need to validate the CA's digital signature found on the server certificate.

Learn more about SSL client from

brainly.com/question/14425531

#SPJ11

8 0
2 years ago
Other questions:
  • Which category of app does word processing software fall into? A. Productivity B. Entertainment C. Social networking D. Educatio
    14·2 answers
  • Alonzo collects bugs. He has created a fascinating display of large insects. Collecting bugs is a(n) _____ to Alonzo.
    10·2 answers
  • Which term refers to actions that you would typically perform on a computer to revive it if it functions in an unexpected manner
    15·2 answers
  • Which of the following is the most common tool that Windows administrators use on the domain controller?
    9·1 answer
  • (BRAINLIEST QUESTION) What are some challenges that will need to be overcome in order for the Internet of Vehicles to become a r
    13·1 answer
  • 8.4 Lesson Practice <br> edhesive quiz
    12·1 answer
  • During the preventive maintenance phase of a project involving a hydraulic power system, an engineer must change a gasket on a p
    14·1 answer
  • Differences between dot_mattix printer and a line printer
    12·1 answer
  • The use of technology to observe a user's actions often without the user's knowledge is known as:
    11·1 answer
  • Why do my airpods keep disconnecting from my laptop
    8·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!