Bubble sort, Data Structure & Algorithms

Assignment Help:

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comparisons in the best and worst cases both are same. Modify the algorithm such  that it will not make the next pass when the array is already sorted.                                                          

Ans:

The bubble sort continues the execution even after an array is sorted. To avoid unnecessary comparisons we add a Boolean variable say switched and initialize it by True in the starting. Along with the "for" loop, we hear add the condition (switched=true) and make it false inside the outer for loop. If a swapping is done then the value of switched is made true. Thus if no swapping has been done in the first pass, then no more comparisons will be done further and the program shall exit.

The algorithm after modifying it in  the  above  stated manner will  be  as follows:-

void bubble(int x[],int n)

{

int j,pass,hold;

bool switched=true;

for(pass=0;pass

{

switched=false;

for(j=0;j

{

switched=true; hold=x[j]; x[j]=x[j+1];

x[j+1]=hold;

}

}

}


Related Discussions:- Bubble sort

Postorder traversal of a binary tree, Postorder traversal of a binary tree ...

Postorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; }; postorder(struct NODE

Determine the space complexity of euclid algorithm, 1)      Why space compl...

1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

If a node having two children is deleted from a binary tree, If a node havi...

If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

#title., Ask quapplication of data structure estion #Minimum 100 words acce...

Ask quapplication of data structure estion #Minimum 100 words accepted#

Database design and sql queries, In assignment, you have already started th...

In assignment, you have already started the process of designing a database for the Beauty Salon mini-case (enclosed again below), mainly in the phase of conceptual database design

Illustrate the visual realism applications, Illustrate the Visual realism a...

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Explain the prim''s minimum spanning tree algorithm, Question 1. Explai...

Question 1. Explain the different types of traversal on binary tree 2. Explain the Prim's minimum spanning tree algorithm 3. Differentiate fixed and variable storage allo

What are expression trees, What are expression trees?  The leaves of an...

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd