Sorting places a important role in programs.Bubble sort is a simple and easy sorting.In this slide , i have explained how it works and how it is better in some cases to other sorting algorithms

Comments

Posting comment...

Premium member

Presentation Transcript

slide 1:

BUBBLE SORT :
Bubble sort is a simple sorting algorithm also called Sinking
algorithm which just goes through a set of data list of numbers or characters
and compares each member with its right neighbour . The pass through the list
is repeated until no more swaps are needed which indicates that the list is
sorted . Although the algorithm is simple It is too slow and impractical for a
large set of data.
PSEUDOCODE :
bubbleAn
while n0 // n is the no of elements
k0
for i1 to n-1
if Ai-1 Ai
swap Ai-1Ai
ki
nk
WORKING :
The bubble sort working with an example :
A 9361842
The length of the array is 7 i.e. let n7.
9 3 6 1 8 4 2
For references : http://comsciguide.blogspot.com/

slide 2:

For 1
st
iteration :
9 3 6 1 8 4 2
3 9 6 1 8 4 2
3 6 9 1 8 4 2
3 6 1 9 8 4 2
3 6 1 8 9 4 2
3 6 1 8 4 9 2
3 6 1 8 4 2 9
After 1
st
iteration we will get a largest element 9 at the last index
of the array . So for the 2
nd
iteration we need not to include it because as in
the sorted list the last element will be the largest one.
For 2
nd
iteration :
3 6 1 8 4 2
3 6 1 8 4 2
For references : http://comsciguide.blogspot.com/

slide 3:

3 1 6 8 4 2
3 1 6 8 4 2
3 1 6 4 8 2
3 1 6 4 2 8
Here u can observe the second largest element 8 in the array is in its
place at n-2 index.
For 3
rd
iteration :
3 1 6 4 2
1 3 6 4 2
1 3 6 4 2
1 3 4 6 2
1 3 4 2 6
For 4
th
iteration :
For references : http://comsciguide.blogspot.com/

slide 4:

1 3 4 2
1 3 4 2
1 3 4 2
1 3 2 4
For 5
th
iteration
1 3 2
1 3 2
1 2 3
For 6
th
iteration :
1 2
As here there is no swaps IF condition wont execute . So nk i.e.
n1 and the program will stop. Finally the sorted array is
1 2 3 4 6 8 9
PERFORMANCE :
Bubble sort has worst-case and average complexity both Оn
2
For references : http://comsciguide.blogspot.com/

slide 5:

where n is the number of items being sorted. There exist many sorting
algorithms with substantially better worst-case or average complexity of
Onlogn . Therefore bubble sort is not a practical sorting algorithm when n is
large.
The positions of the elements in bubble sort will play a large part in
determining its performance . Large elements at the beginning of the list do not
pose a problem as they are quickly swapped . Small elements towards the end
however move to the beginning extremely slowly. This has led to these types of
elements being named rabbits and turtles respectively.
It has a special feature that the largest element at last index gets
sorted first with smaller elements taking longer to move to their correct
positions.
The only significant advantage that bubble sort has over most other
implementations even quicksort but not insertion sort is that the ability to
detect that the list is sorted in efficient way .When the list is already sorted
best-case the complexity of bubble sort is only On. By contrast most other
algorithms even those with better average-case complexity perform their
entire sorting process on the set and thus are more complex.
ANALYSIS :
U will be knowing that we do sort for a set of numbers.
Suppose if u have given array of elements which is already sorted and
one element is added to this..U will be having doubt where we have to
For references : http://comsciguide.blogspot.com/

slide 6:

add this elementat the begining or ending of array..What is that
complexity for this sorting if we add new element at the last..
Take a look with an example :
Lets take this array which is already sorted.
1 2 3 4 6 8 9
Consider the case of adding the new number assume 5 at
the begining of the array .
The new array becomes
5 1 2 3 4 6 8 9
For 1
st
iteration :
5 1 2 3 4 6 8 9
1 5 2 3 4 6 8 9
1 2 5 3 4 6 8 9
1 2 3 5 4 6 8 9
For references : http://comsciguide.blogspot.com/

slide 7:

1 2 3 4 5 6 8 9
// the array is sorted and
k5 ..so n5
1 2 3 4 5 6 8 9
1 2 3 4 5 6 8 9
1 2 3 4 5 6 8 9
FOR 2ND ITERATION :
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
As for 2
nd
iteration no swaping occurs i.e. kn1. So there is no chance
of 3
rd
iteration and the program exits.
Now consider the case of adding the new number assume 5
at the ending of the array .
The new array becomes
For references : http://comsciguide.blogspot.com/

1 2 3 4 5 6 8 9
1 2 3 4 5 6 8 9
As for 4
th
iteration no swaping occurs i.e. kn1. So there no
chance of 5
th
iteration and the program exits.
From the analysis we observe that by adding an element
at the front of index the cost of running time is less as compared to
the cost of running time for the case of adding element at the last.
IN PRACTICE :
Bubble sort is one of the simplest sorting algorithm to implement
and easy to understand . Due to its simplicity bubble sort is often used to
introduce the concept of an algorithm or a sorting algorithm to introductory
students.
But due its On
2
complexity It will not be efficient for the case of
large lists .Its On
2
complexity means that its efficiency decreases dramatically
on lists of large number of elements . Even among simple On
2
sorting
algorithms like insertion sort are usually considerably more efficient.
For references : http://comsciguide.blogspot.com/

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.