Bubble sort, Data Structure & Algorithms

Assignment Help:

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm.

In this method, adjacent members of list to be sorted are compared. If item over the top is greater than the item instantly below it, then they are swapped. This procedure is carried on until the list is sorted.

The detailed algorithm is like as:

Algorithm: BUBBLE SORT

1. Begin

2. Read the n elements

3. for i=1 to n

              for j=n downto i+1

               if a[j] <= a[j-1]

              swap(a[j],a[j-1])

4. End // of Bubble Sort

Total number of comparisons in Bubble sort will be:

= (N-1) +(N-2) . . . + 2 + 1

= (N-1)*N / 2 =O(N2)

This inefficiency is because of the fact that an item moves only to the next position in each pass.


Related Discussions:- Bubble sort

Red black tree, red black tree construction for 4,5,6,7,8,9

red black tree construction for 4,5,6,7,8,9

Search engines - applications of linear and binary search, Search engines e...

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Quicksort and bubble sort algorithms, Task If quicksort is so quick, w...

Task If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your

Binary trees, A binary tree is a special tree where each non-leaf node can ...

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Applications of avl trees, AVL trees are applied into the given situations:...

AVL trees are applied into the given situations: There are few insertion & deletion operations Short search time is required Input data is sorted or nearly sorted

Array, how to define the size of array

how to define the size of array

Recursive implementation of binary tree traversals, There are three typical...

There are three typical ways of recursively traversing a binary tree. In each of these, the left sub-trees & right sub-trees are visited recursively and the distinguishing feature

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Structured programming, What do you understand by term structured programmi...

What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

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