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
Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.

Multilist Representation of graph

sdsd.

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c

write an algorithm for the gpa of six students

Binary Space Partition A binary space-partitioning (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front,

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?

Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

In a doubly linked list, also called as 2 way list, each node is divided into 3 parts. The first part is called previous pointer field. It contains the address of the preceding