Scribd
Upload
19 views9 pages

Bubble 1

Uploaded by

namyab2009
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views9 pages

Bubble 1

Uploaded by

namyab2009
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

BUBBLE SORTING

CONNECTING

Learning Intention
• Sorting is a process in which the elements of an
array are arranged in either ascending or descending
order.

• It is necessary to learn sorting techniques as it is


easier and faster to locate items in a sorted array.
Lesson Objectives
• To understand Bubble sort
• To analyze Bubble sort
• To create a code for sorting the elements in an array using Bubble
sort
Success Criteria
At the end of this unit, you should be able to:

✓Sort Numerical, Character, Boolean and String Type of data in


Ascending order or Descending order using sorting techniques like
Bubble sort and Selection sort.

✓Predict the status of the array during or after the sorting process
INTRODUCTION
Bubble Sort
In this sorting technique, adjacent
elements of an array are compared
repeatedly to check if they are in the correct
position and swapped if they are not in
correct position. This process is repeated
until all the elements in the array are sorted.
Bubble Sort Technique
• In this technique, to start with, the first and the second elements are
compared and swapped if they are out of order. Then the second and the
third elements are compared and swapped if they are out of order. This
process continues until the last two elements are compared and
swapped if they are out of order. This is called Pass 1.

• A pass is defined as one full trip through the array, comparing and if
necessary, swapping, adjacent elements. Several passes must be made
through the array before it is finally sorted.

• When the first pass through the array is complete, the smallest value (if
the array is being sorted in descending order) or the largest value (if the
array is being sorted in Ascending order) is placed in the last index
position.

• In the second pass, the process starts all over again, but this time the
element in the last position will not be compared as it has been placed
in the correct position. The process stops when no swaps are needed,
which indicates that the array is sorted.
Bubble Sort Technique contd…
Let us take the array of numbers 5, 1, 4, 2, 8, and sort the array in Ascending order.
In each step, elements written in bold are being compared.
Pass 1
5 1 4 2 8 5 and 1 swapped since 5 > 1
1 5 4 2 8 5 and 4 swapped since 5 > 4
1 4 5 2 8 5 and 2 swapped since 5 > 2
1 4 2 5 8 No swap since 5<8

Pass 2
1 4 2 5 8 No swap since 1<4
1 4 2 5 8 4 and 2 swapped since 4 > 2
1 2 4 5 8 No swap since 4<5
5 will not be compared with 8, as 8 is already in the correct position
Now, the array is already sorted, but the algorithm does not know if it is completed.
The algorithm needs one whole pass without any swap to know it is sorted.

Pass 3

1 2 4 5 8 No swap since 1<2


1 2 4 5 8 No swap since 2<4
4 will not be compared with 5, and 5 will not be compared with 8, as 5 and 8 are already
in their correct positions
Bubble Sort Technique contd…

Bubble sort showing Pass1. Bubble sort is also known as a Sinking sort algorithm as
the smallest element or the largest element (as the case may be) sinks to the end of
the list.
Final Bubble Sort Program
class bubblsort // Bubble sort - sorting In Ascending order
{ public static void main( ) {
int n[ ]= {5,1,11,-5,16, 2,12,14};
int x,y, tmp;
for(x=0; x<n.length; x++)
{ boolean chk=true; // flag variable to indicate status n.length-1 is required because the element in the last position
cannot be compared with the next element
for( y=0; y<n.length-1-x; y++)
{ if(n[y]>n[y+1]) // comparing adjacent elements In bubble sort, the smallest or the largest element settles at the bottom of the
array after every round of comparison (PASS). Whereas in this program
{ chk=false; // indicates swapping has happened elements in all the positions are compared repeatedly even though they are in
tmp=n[y]; the correct position.
Moreover, after a comparison if there is no swapping, it indicates that the array
n[y]=n[y+1]; has been sorted and further comparisons are not required. This aspect has not
been taken care of in the program.
n[y+1]=tmp; } The program in the next slide is more efficient as the number of comparisons
are less and the program terminates, as soon as the array is sorted.
} // y loop
if(chk) // if chk remains true, it means no swapping so the outer loop is terminated
break;
} // x loop
// displaying array
for(x=0;x<n.length;x++)
System.out.println(n[x]);
} }

You might also like