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(n) _____ exists when there are functional dependencies such that XY is functionally dependent on WZ, X is functionally depende
Nat2105 [25]

A partial dependency exists.

We have two types of dependency. The partial dependency and the transitive dependency.

The answer here is partial dependency. It occurs when the attribute only depends on some parts of the element. In such attribute, the primary key is the determinant.

It can be shown as;

XY→WZ , X→W and XY is the primary key or the only candidate key

Read more at brainly.com/question/9588869?referrer=searchResults

3 0
3 years ago
Read 2 more answers
Use the variables k and total to write a while loop that computes the sum of the squares of the first 50 counting numbers, and a
pshichka [43]
Int   k=0.total=0;
while(k++<50)
    total+=k*k;
    

5 0
3 years ago
It's best to use assertive speech when you<br> I want to show respect. *<br> True<br> False
mestny [16]

Answer:

True

Explanation:

Hope this helps :)

6 0
3 years ago
Read 2 more answers
Mobile devices need to work within limited screen space .
zloy xaker [14]
True. Mobile devices need to work within limited screen space. Mobile devices are designed to be portable and designed to be carried around without hassle. Mobile devices are used for personal activities such as talking privately, chatting and many more that is why it is designed to be small.
3 0
3 years ago
Write a Python 3 program to read from a .csv file containing rates from power companies. Your program should determine the avera
aliya0001 [1]

Answer:

In python:

file = open("rates.csv", "r")

ratecount = 0

ratesum = 0

mylist = []

rates = file.readlines()

for nums in rates:

     num = nums.rstrip('\n')

     mylist.append(int(num))

     for i in num:

           ratesum= ratesum + int(i)

           ratecount = ratecount + 1

print("Maximum Rate: "+str(max(mylist)))

print("Minimum Rate: "+str(min(mylist)))

print("Average Rate: "+str(ratesum/ratecount))

Explanation:

This opens the csv file

file = open("rates.csv", "r")

This initializes the number of rates in the file

ratecount = 0

This initializes the sum of the rates

ratesum = 0

This initializes an empty list

mylist = []

This reads the rates into lines

rates = file.readlines()

This iterates through the rates (as a string)

for nums in rates:

This removes the newline character \n in the rates

     num = nums.rstrip('\n')

This appends the rates (as an integer) to the empty list

     mylist.append(int(num))

The following counts the rates in the file and also sum them up

<em>      for i in num: </em>

<em>            ratesum= ratesum + int(i) </em>

<em>            ratecount = ratecount + 1 </em>

This prints the maximum of the rates

print("Maximum Rate: "+str(max(mylist)))

This prints the minimum of the rates

print("Minimum Rate: "+str(min(mylist)))

This calculates and prints the average rate

print("Average Rate: "+str(ratesum/ratecount))

6 0
3 years ago
Other questions:
  • 20 Points!! Please hurry!!
    9·1 answer
  • How do you represent images in binary
    6·2 answers
  • I need some help pleas hurry
    5·1 answer
  • You are attempting to upgrade a Windows Server 2008 R2 server to Windows Server 2016 Standard. What must be done in order to acc
    5·1 answer
  • Given the following structure and variable definitions, struct customer { char lastName[ 15 ]; char firstName[ 15 ]; unsigned in
    6·1 answer
  • Always follow the routine "clean up while in use and clean up before keeping it".
    6·1 answer
  • Who is famous for his three laws of robotics?
    9·1 answer
  • In order to view a page break what should you do
    8·1 answer
  • Given the following declaration, what is the value of b[ 1 ][ 0 ]? int b[ 2 ][ 2 ] = { { 1 }, { 3 , 4 } };
    13·1 answer
  • What are some of the most common obstacles in video games?
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!