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
need an expert to help me with the assignment

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited. Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if

the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

State the ways to construct container taxonomy There are several ways that we could construct our container taxonomy from here; one way that works well is to make a fundamental

Suppose you are given the results of 5 games of rock-paper-scissors. The results are given to you on separate pieces of paper; each piece says either 'A' if the first person won, o

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

algorithm for multiplication of two sparse matrices using link list

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position

Double Linked List In a doubly linked list, also known as 2 way lists, each node is separated into 3 parts. The first part is called last pointer field. It has the address of t