Bubble sort, Data Structure & Algorithms

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;

}

}

}

Posted Date: 7/10/2012 4:59:23 AM | Location : United States







Related Discussions:- Bubble sort, Assignment Help, Ask Question on Bubble sort, Get Answer, Expert's Help, Bubble sort Discussions

Write discussion on Bubble sort
Your posts are moderated
Related Questions
data structure for multiqueue

What is Space complexity of an algorithm? Explain.

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

This unit dealt along with the methods of physically storing data in the files. The terms fields, records & files were described. The organization types were introduced. The sev

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

the deference between insertion,selection and bubble sort

The data structure needed for Breadth First Traversal on a graph is Queue


Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's