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
g Create a program that reads a list of states from an input file, puts them in order, and displays the sorted list to the user.
mixas84 [53]

Answer:

Check the explanation

Explanation:

# Step 1

the first thing to execute will be......

f = open("states.txt")

# Step 2

the second step is......

states = []

for line in f:

   states.append(line.strip())

# Step 3:

the third step is to......

for state in sorted(states):

   print(state)

f.close()

3 0
3 years ago
True or Flase<br><br> In C++, the body of a for loop may never run even once.
stiks02 [169]

Answer: True

Explanation: For loop is used in the C++ programming is defined as the statement that defines about the flow control .This loop works under some condition that is considered.

For loop is evaluated to execute for one time if the statement condition is true but there are also chances of no execution at all because of the incorrect condition. So, for loop might not run even once in that condition.Thus , the statement given is true.

3 0
3 years ago
Which of the following is a true statement?
m_a_m_a [10]
Let me help you!
Did you know that both plants and animals undergo cellular respiration? The reason behind that is because both organims needs to get energy and to expel wastes.

Therefore, the correct answer for your question is: <span>C.Cellular respiration occurs in both plant and animal cells.

I hope that helped you! :></span>
4 0
3 years ago
Three ways to increase value of a variable ​
krok68 [10]

Answer:

Three ways to increase the value of variable are given below. To eleborate the answer, I am taking a variable x that need to be increase.

  1. x=x+1
  2. x++
  3. x+=1

Explanation:

There are three ways to increase the value of variable.

1. x= x+1

In this case, each time value of x (variable) is incremented and stored in that variable. This equation increase the value of x by 1 each time. For Example

if x=1

then in first iteration

x= x+1 = 2;

If we want to increase the value of x by more than 1, we can add that value with x, as x+2, x+3 and so on.

2. x++

This will increment the value of x by 1. If we use this equation multiple time in program, each time it will increase 1 in value of x.

3. x+=1

This also works same as equation 1. It will increment 1 in this form and can be changed with 2, 3 and so on.

6 0
3 years ago
Consider the key success factors of B2C. Is it only IT? What is most important?​
Ad libitum [116K]

Jsjfu zzer jsusuc888 kksss

6 0
3 years ago
Other questions:
  • What operating system was most commonly used by early personal computers? Apple Mac MS-DOS Windows
    6·2 answers
  • what is the restaurant with the black pom tree and yellow backround three letter name from hi guess the restaurant
    14·2 answers
  • What are the two components that make up the chipset?
    15·1 answer
  • You received a call form a user who brought her own device to the office but cannot find or connect to the company WLAN. The lap
    12·1 answer
  • How to study program ?
    11·1 answer
  • Can anyone please help with this programming code in python num= 7 if num &gt; 3: print(“3”) if num &lt; 5: print(“5”) if num ==
    6·1 answer
  • PLEASE HURRY!!!
    11·1 answer
  • WHAT ARE SOME PROS AND CONS OF HYDROGEN FUELL CELLS
    11·1 answer
  • What is destination email address​
    8·1 answer
  • The pci express version 4.0 can provide up to what amount of throughput with 16 lanes for data?
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!