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
A user has a new web email account and asks a technician for help with setting up email on a tablet. The user would like for the
frutty [35]

Answer:

B

Explanation:

POP3 protocol is an email protocol that works by downloading and storing emails onto a user's device or tablet.

7 0
3 years ago
7. Malware could A. cause a system to display annoying pop-up messages B. be utilized for identity theft by gathering personal i
beks73 [17]

Answer:

D

Explanation:

Malware can be used for many things, a click of a button can send complete access to the attacking system. Malware comes in all formes and powers.

4 0
2 years ago
Percentage-wise, which renewable energy source is used most?
Natasha2012 [34]
C)Hydroelectric I believe.
5 0
3 years ago
Is an applications program is a program designed to perform a specific task for specific users
Vika [28.1K]

Answer:

application software or tailored software

6 0
3 years ago
Help me<br>please answers this questions<br>​
kobusy [5.1K]

Answer:

RSI stands for repeating similar movements

3 0
2 years ago
Other questions:
  • In an interview, an appropriate response to "What is an example of one of your
    13·2 answers
  • In order to do a binary search on an array Group of answer choices you must first do a sequential search to be sure the element
    5·1 answer
  • 1 megabyte is equal to 1024 gigabyte. True/False​
    11·2 answers
  • Suppose that we can improve the floating point instruction performance of machine by a factor of 15 (the same floating point ins
    13·1 answer
  • Anyone got the edmentum computer programming post test answers?
    6·1 answer
  • Psychographics may also be called A. personality analytics. B. social group dynamics. C. lifestyle analysis. D. opinion insight.
    6·1 answer
  • What is the positional weigh of the digit 7 in the octal number 7642 ?​
    15·1 answer
  • Help help help help help!!!
    7·1 answer
  • What are some qualities of a good game critic? What are some qualities of a bad game critic?
    7·1 answer
  • In this lesson, you learned how to create reports and how to display them in a Web application. You will use the same chinook da
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!