Bubble Sort


Wolmer’s Trust High School for Girls

CAPE COMPUTER SCIENCE

 

Grade:  11                                          Teacher:  Mrs. McCallum-Rodney

 

TOPIC : BUBBLE SORT

 

·         The Bubble Sort (also known as the sinking sort) is so called because the smaller values gradually “bubble” their way to the top of the array like air bubbles rising in water, while the larger values sink to the bottom of the array. 

 

·         The technique is to make several passes through the array. The number of passes in the array is equal to the size of the array minus 1.

 

·         On each pass, successive pairs of elements are compared.  For example, in a 6-element array, for each pass the pairs that will be compared are:

 

o       0 and 1

o       1 and 2

o       2 and 3

o       3 and 4

o       4 and 5

     

       The number of comparisons is equal to the size of the array minus 1.

 

·         If a pair is in increasing order (or if the values are identical), we leave the values as they are.  If a pair is in decreasing order, their values are swapped in the array.

 

             Arr

0

12

1

14

2

3

4

5

 Because element 0 and 1 are in increasing order a swap is not needed

 

             Arr

0

23

1

14

2

3

4

5

 Because element 0 and 1 are in decreasing order a swap is needed

                 

                  To Swap….    Temp = Arr[0]

                                        Arr[0]=Arr[1]

                                        Arr[1] = temp

 

 

 

 


 

DIAGRAMMATIC REPRESENTATION OF THE BUBBLE SORT

 

Question: Show how a six-element array is sorted using a bubble sort.  The values in the array are 4, 1, 10, 4, 11 and 0.

 

PASS 1

0

4

Swap

 

0

1

 

0

1

 

 

Swap

0

1

 

 

 

 

Leave

0

1

 

0

1

1

1

1

4

Leave

1

4

1

4

1

4

 

1

4

2

10

2

10

 

2

10

2

4

2

4

 

2

4

3

4

3

4

 

3

4

3

10

3

10

 

3

10

4

11

4

11

 

4

11

4

11

4

11

Swap

4

0

5

0

5

0

 

5

0

5

0

5

0

5

11

 

PASS 2

0

1

Leave

 

0

1

 

0

1

 

 

Leave

0

1

 

 

 

 

Swap

0

1

 

0

1

1

4

1

4

Leave

1

4

1

4

1

4

 

1

4

2

4

2

4

 

2

4

2

4

2

4

 

2

4

3

10

3

10

 

3

10

3

10

3

0

 

3

0

4

0

4

0

 

4

0

4

0

4

10

Leave

4

10

5

11

5

11

 

5

11

5

11

5

11

5

11

 

PASS 3

0

1

Leave

 

0

1

 

0

1

 

 

Swap

0

1

 

 

 

 

Leave

0

1

 

0

1

1

4

1

4

Leave

1

4

1

4

1

4

 

1

4

2

4

2

4

 

2

4

2

0

2

0

 

2

0

3

0

3

0

 

3

0

3

4

3

4

 

3

4

4

10

4

10

 

4

10

4

10

4

10

Leave

4

10

5

11

5

11

 

5

11

5

11

5

11

5

11

 

 

PASS 4

0

1

Leave

 

0

1

 

0

1

 

 

Leave

0

1

 

 

 

 

Leave

0

1

 

0

1

1

4

1

4

Swap

1

0

1

0

1

0

 

1

0

2

0

2

0

 

2

4

2

4

2

4

 

2

4

3

4

3

4

 

3

4

3

4

3

4

 

3

4

4

10

4

10

 

4

10

4

10

4

10

Leave

4

10

5

11

5

11

 

5

11

5

11

5

11

5

11

 

PASS 5

0

1

Swap

 

0

0

 

0

0

 

 

Leave

0

0

 

 

 

 

Leave

0

0

 

0

0

1

0

1

1

Leave

1

1

1

1

1

1

 

1

1

2

4

2

4

 

2

4

2

4

2

4

 

2

4

3

4

3

4

 

3

4

3

4

3

4

 

3

4

4

10

4

10

 

4

10

4

10

4

10

Leave

4

10

5

11

5

11

 

5

11

5

11

5

11

5

11

 

Description/Narrative of the Bubble Sort Algorithm

 

1.      The size of the array should be stored in a variable.  If the size of the array is 6, then the instruction is:

size = 6

2.      A repetition structure – FOR LOOP - is then needed to ensure that the number of passes through the array do not exceed the size of the array minus one.

FOR phase = 1 TO size-1

3.        Within the for loop, the following steps will take place:

a.       The first element position in the array will need to be stored.

elementpos = 0

b.      Another for loop will be implemented to control the number of comparisons that will take place for each pass.  The number of comparisons is the same for each pass, which is the size of the array minus one.

FOR compare = 1 TO size - 1

c.       Within the for loop in 3(b), the following steps are needed:

                                                  i.      A selection structure – IF-ENDIF – to determine if the value stored in elementpos is greater than the value store in elementpos plus one.

IF arr[elementpos] > arr[elementpos + 1]

                                                ii.      If the answer to 3c(i) is true, then a swap should take place.  A temporary variable will be needed to store the value that is in elementpos; then the value in elementpos plus 1 will be stored in elementpos; afterwards the value in temp will be stored in elementpos + 1.

temp = arr[elementpos]

arr[elementpos] = arr[elementpos+1]

arr[elementpos+1] = temp

                                              iii.      When the selection structure is exited, elementpos will need to imcrement by 1.

elementpos = elementpos + 1

d.      Increment compare by one, the loop is exited in 3(b), when compare is greater than size minus 1.

4.      Increment phase by one, then the for loop in 2 is exited if phase exceed size -1.

5.      The sort is then completed.

 

 

 

 

 

Make a Free Website with Yola.