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 string abstract data type operations, Explain about the S...

Explain about the String Abstract data type operations Symbol ADT has no concatenation operations, but presuming we have a full-featured String ADT, symbols can be concatenated

Determination of time complexity, Determination of Time Complexity The...

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

Difference between array and abstract data types, Difference between array ...

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Lists, In the previous unit, we have discussed arrays. Arrays are data stru...

In the previous unit, we have discussed arrays. Arrays are data structures of fixed size. Insertion and deletion involves reshuffling of array elements. Thus, array manipulation

Explain arrays, Arrays :- To execute a stack we need a variable called top,...

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Determine the types of java, Determine the types of JAVA Java has two p...

Determine the types of JAVA Java has two parts... 1. Core language -- variables, arrays, objects o Java Virtual Machine (JVM) runs the core language o Core language is

Creation of a circular linked list, Program: Creation of a Circular linked ...

Program: Creation of a Circular linked list ALGORITHM (Insertion of an element into a Circular Linked List) Step 1        Begin Step 2      if the list is empty or new

Define the term counting - pseudocode, Define the term counting - Pseudocod...

Define the term counting - Pseudocode Counting in 1s is quite simple; use of statement count = count + 1 would enable counting to be done (for example in controlling a repeat

Interest, I =PR/12 Numbers of years .Interest rate up to 1yrs ...

I =PR/12 Numbers of years .Interest rate up to 1yrs . 5.50 up to 5yrs . 6.50 More than 5 yrs . 6.75 design an algorithm based on the above information

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