Schedule‎ > ‎

10A: Bubble Sort, Break, Continue and Pointers

Questions, Answers and Review

  • Questions from last class? 
  • Questions about homework?

Sorting and Sorting Algorithms

Sorting is one of the most important jobs that a program does. In this class we'll build on the array operations from last class. You will implement code that sorts the contents of an array. 

Learner Outcomes

  • Be able to sort input data
  • Use sorting functions in C++

Sorting Algorithms

There are many different sorting algorithms. You saw Insertion Sort in the last lesson.  Sorting algorithms mostly vary by how fast they operate, which is expressed in terms of the number of items they have to sort. The algorithm we'll learn in this class is among the worst sorting algorithms in terms of performance. The time it takes to sort a list is proportional to the square of the number of elements in the list. That's poor. However, it is very easy to code and as long as your list is small you won't notice it's performance. 

Bubble Sort 

Bubble sort works by looping over a list again and again while swapping elements that are out of order. Wikipedia has a great illustration of bubble sort. That's shown on the right (click the image to see the animation).

Here's the first two passes step-by-step:

 Pass  Step  Before  After  Explanation 
 0  0     { 6, 5, 3, 1, 8, 7, 2, 4 }  { 5, 6, 3, 1, 8, 7, 2, 4 }  6 > 5: Swap 5 and 6
 0  1  5, 6, 3, 1, 8, 7, 2, 4 }  5, 36, 1, 8, 7, 2, 4 }  6 > 3: Swap 3 and 6
 0  2  5, 36, 1, 8, 7, 2, 4 }  5, 3, 1, 6, 8, 7, 2, 4 }  6 > 1: Swap 1 and 6
 0  3  5, 3, 1, 6, 8, 7, 2, 4 }  5, 3, 1, 68, 7, 2, 4 }  No action
 0  4  5, 3, 1, 6, 8, 7, 2, 4 }  5, 3, 1, 6, 78, 2, 4 }  8 > 7: Swap 8 and 8
 0  5  5, 3, 1, 6, 78, 2, 4 }  5, 3, 1, 6, 7, 2, 8, 4 }  8 > 2: Swap 2 and 8
 0  6  { 5, 3, 1, 6, 7, 2, 8, 4 }  { 5, 3, 1, 6, 7, 2, 48 }  8 > 4: Swap 4 and 8
 1  0  { 5, 3, 1, 6, 7, 2, 4, 8 }  { 3, 5, 1, 6, 7, 2, 4, 8 }  5 > 3: Swap 3 and 5
 1  1  { 3, 51, 6, 7, 2, 4, 8 }  { 3, 1, 5, 6, 7, 2, 4, 8 }  5 > 1: Swap 5 and 1
 1  2  { 3, 156, 7, 2, 4, 8 }  { 3, 156, 7, 2, 4, 8 }  No action
 1  3  { 3, 1, 5, 67, 2, 4, 8 }  { 3, 1, 5, 67, 2, 4, 8 }  No action
 1  4  { 3, 1, 5, 6, 72, 4, 8 }  { 3, 1, 5, 6, 2, 7, 4, 8 }  7 > 2: Swap 2 and 7
 1  5  { 3, 1, 5, 6, 274, 8 }  { 3, 1, 5, 6, 2, 4, 7, 8 }  7 > 4: Swap 4 and 7
 1  6  { 3, 1, 5, 6, 2, 4, 78 }  { 3, 1, 5, 6, 2, 4, 78 }  No action

Notice how the larger numbers "bubble" to the right as the swapping operation picks them up. 
More information: Bubble Sort: YouTube video from CS50.tv

Exercise 1. (1 hr) (bubbleSort.ino)


Work alone or with your pair partner to implement bubble sort.

Use the following code to get started:

#include <ArduinoSTL.h>
using namespace std;


void setup() {
  Serial.begin(9600);
}

void printList(const vector<int> &list) {
  cout << "{ " ;
  for (int i=0; i<list.size(); i++) {
    cout << list[i] << " ";
  }
  cout << "}" << endl;
}

void bubbleSort(vector<int> &list) {

  // TODO: sort the list
}


void loop() {
  cout << "Enter some integers separated by spaces (enter zero when you're done):" << endl;
  vector<int> list; 
  int num;
  cin >> num;
  while (num != 0) {
    list.push_back(num);
    cin >> num;   
  }
  cout << "Unsorted List: ";
  printList(list);
  bubbleSort(list);
  cout << "Sorted List: ";
  printList(list);
}

Here is some pseudocode for BubbleSort:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   for i = 1 to n-1 inclusive do
     for j = 1 to n-1 inclusive do
       if A[j-1] > A[j] then /* if this pair is out of order */
         swap( A[j-1], A[j] )
       end if
     end inner for
   until outer for
end procedure

Helpful Hints

  • Make sure the line endings in the Serial Monitor are set to "Newline".
  • In order to swap two array values you need a temporary variable. 
  • You will need a for loop inside another for loop. 
  • Notice that each for loop goes through one fewer element than the size of the array. In the above example the array has eight elements and each pass is only seven steps
Submit your bubbleSort.ino on Canvas

Extra Challenge

In your bubble sort function, add a call to printList() after every pass of the outer loop.


Break and Continue Statements

break  and continue  alter the normal  flow of a program
Sometimes you want to skip the execution of a loop or terminate it immediately
Example:  You want to loop through data until you find someone of age 20   (break)
Example:  Loop through data of all people except those of age 60.    (continue)

break statement

void loop() {

    float number, sum = 0.0;

    // flag is set by an external source - assume always true

    while (flag)

    {

        cout << "Enter a number: 0 to terminate: " << endl;

        cin >> number;

       

        if (number != 0.0)

        {

            sum += number;

        }

        else

        {

            // terminates the while loop if number equals 0.0

            break;

        }

    }

    cout << "Sum = " << sum << endl;

}

continue statement

Continue to the next iteration of the loop
Print numbers from 1 to 10, but not 6 or 9

 

   for (int i = 1; i <= 10; ++i)    {       

      if ( i == 6 || i == 9)        {           

        continue;       

       }       

    cout << i << "\t";   

}


break vs. continue vs. return

break terminates the current loop and execution starts at the first statement after the loop
continue skips to the next iteration of the loop
a return statement ends the current function and returns to the function caller.

Summary

  • We often need to sort lists of data like exam scores
  • One algorithm we can use for sorting is bubble sort
  • Bubble sort is useful because it has compact code and is easy to memorize
  • While it does not have the best performance, there are worse algorithms (see Stooge Sort)
  • The following is the psuedocode for Bubble Sort (source:Wikipedia with modifications)
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   for i = 1 to n-1 inclusive do
     for j = 1 to n-1 inclusive do
       if A[j-1] > A[j] then /* if this pair is out of order */
         swap( A[j-1], A[j] )
       end if
     end inner for
   until outer for
end procedure
  • As we can see, bubble sort is a set of nested loops with an if-statement to test when to swap elements
  • Bubble sort may be optimized fairly easily
  • However, it is still a fairly slow algorithm whose speed decreases quickly on lists of more than a few elements

^ top

Pointers

Pointer slides HERE


^ top

Wrap Up and Reminders

  • For the next homework, see the schedule
  • When class is over, please shut down your computer.
  • Complete unfinished exercises from today before the next class meeting

^ top



Comments