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

Search on a heap file, Consider the file " search_2013 ". This is a text fi...

Consider the file " search_2013 ". This is a text file containingsearch key values; each entry is a particular ID (in the schema given above). You are tosimulate searching over a h

Define rule-based expert system, 1. Define the following terms in a rule-ba...

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

Define the terms - key attribute and value set, Define the terms   ...

Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr

Representation of linked list in memory, Representation of Linked list in M...

Representation of Linked list in Memory:- Each node has an info part and a pointer to the next node also known as link. The number of pointers is two in case of doubly linked

Implement a min-heap, Description A heap is an efficient tree-based data...

Description A heap is an efficient tree-based data structure that can be used as a priority queue. Recall that the abstract data type of a priority queue has the following opera

Grounded header link list and a circular header link list, What is the diff...

What is the difference between a grounded header link list and a circular header link list? A header linked list is a linked list which always having a special node, known as t

Sorting, Sort the following array of elements using quick sort: 3, 1, 4, 1,...

Sort the following array of elements using quick sort: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8.

Stack, Explain the array and linked list implementation of stack

Explain the array and linked list implementation of stack

find shortest path from a to z using dijkstra''s algorithm., Q.  In the gi...

Q.  In the given figure find the shortest path from A to Z using Dijkstra's Algorithm.    Ans: 1.  P=φ;  T={A,B,C,D,E,F,G,H,I,J,K,L,M,Z} Let L(A)

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