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

The quick sort algorithm exploit design technique, The quick sort algorithm...

The quick sort algorithm exploit design technique Divide and Conquer

State in brief about assertion, State  in brief about assertion Asser...

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Implementation of stack using arrays, A Stack has an ordered list of elemen...

A Stack has an ordered list of elements & an array is also utilized to store ordered list of elements. Therefore, it would be very simple to manage a stack by using an array. Thoug

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure...

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

What are the dynamic arrays, What are the Dynamic arrays Dynamic arrays...

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

Graph, multilist representation of graph

multilist representation of graph

Comp. sci algorithms, 1. develop an algorithm which reads two decimal numbe...

1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which

Quick sort, This is the most extensively used internal sorting algorithm. I...

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

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