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 tools, skills, knowledge, and machines created and used by humans is known as.
miskamm [114]

Answer:

Human capital

Explanation:

It means the economic value of workers experience and skills

7 0
2 years ago
En la historia del Computador porque se caracteriza la primera generación? *
Nadusha1986 [10]

D. Por el uso de tubos de vacio.

8 0
3 years ago
Determine whether the compound condition is True or False.
Vlada [557]

The  compound condition are:

  • 7<12 or 50!=10 is false
  • 7<12 and 50<50 is false
  • not (8==3) is true

<h3>What is compound condition?</h3>

A compound statement is known to be one that shows up as the body of another statement, e.g. as in if statement.

The  compound condition are:

  • 7<12 or 50!=10 is false
  • 7<12 and 50<50 is false
  • not (8==3) is true

Learn more about compound condition  from

brainly.com/question/18450679

#SPJ1

8 0
1 year ago
How can E-Commerce Portals ensure Security of online Transactions by Customers?
beks73 [17]
Ffkjlfdhaslkjfhlaksdfhlkajsdfh
6 0
3 years ago
Write a procedural programming loop.. Your loop should start variable n with a value of 10 and count down to zero. The loop shou
anastassius [24]

Answer:

//Here is the for loop in C.

for(n=10;n>0;n--)

{

   printf("count =%d \n",n);

}

Explanation:

Since C is a procedural programming language.Here if a loop that starts with n=10; It will run till n becomes 0. When n reaches to 0 then loop terminates otherwise it  print the count of n.

// here is code in C++.

#include <bits/stdc++.h>

using namespace std;

// main function

int main()

{  // variables

int n;

// for loop that runs 10 times

// when n==0 then loop terminates

for(n=10;n>0;n--)

{

   cout<<"count ="<<n<<endl;

}

return 0;

}

Output:

count =10

count =9

count =8

count =7

count =6

count =5

count =4

count =3

count =2

count =1

3 0
3 years ago
Other questions:
  • A programmer wrote the code segment below to display the average of all the elements in a list called numbers. There is always a
    8·1 answer
  • What microprocessor was the first to be processable<br> ?
    14·1 answer
  • Linguist study
    9·1 answer
  • Create a query that will list all technician names, employee numbers, and year hired in order by year hired (Newest to Oldest).
    5·1 answer
  • On other questions, how do I write my own question, without commenting on others questions? It is only allowed two, I think, the
    13·1 answer
  • CHALLENGE 7.1.1: Initialize a list. ACTIVITY Initialize the list short.names with strings 'Gus', Bob, and 'Ann'. Sample output f
    9·1 answer
  • I'm not sure how to do these. By the way, it has to be python.
    13·1 answer
  • PLZZZ HELP!!!
    9·1 answer
  • Give me two reasons why return statements are used in code.
    10·2 answers
  • Define a function that will return the length of a list
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!