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

Explain about the abstract data type, Explain about the Abstract data type ...

Explain about the Abstract data type Abstract data type (ADT) A set of values (the carrier set) and operations on those values

Program, circular queue using c

circular queue using c

Row major representation, Row Major Representation In memory the primar...

Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

In order post order, illlustraate the construction of tree of a binary tree...

illlustraate the construction of tree of a binary tree given its in order and post order transversal

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)...

Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Determine the critical path and the expected completion, The information in...

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total

Algorithm, what algorithms can i use for the above title in my project desi...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

State warnock algorithm, Warnock's Algorithm An interesting approach to...

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

Graph traversal schemes, Various graph traversal schemes Graph Traversa...

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

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