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
What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally

differences between direct and indirect recursion

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

Which sorting algorithm is easily adaptable to singly linked lists? Simple Insertion sor t is easily adabtable to singly linked list.

What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

The Euclidean algorithm is an algorithm to decide the greatest common divisor of two positive integers. The greatest common divisor of N and M, in short GCD(M,N), is the largest in

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_

I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.