Home‎ > ‎CS 11M‎ > ‎

Sorting Algorithms

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 and vector operations from last class. You will implement code that sorts the contents of a vector or an array. 

Sorting Algorithms

There are many different sorting algorithms. They 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. 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. Look at the animation below from Wikipedia to see how bubble sort works. 
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, 3, 6, 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, 7, 8, 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, 1, 56, 7, 2, 4, 8 }  { 3, 1, 56, 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, 2, 74, 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

Pseudocode 

Pseudocode is a way of summarizing a procedure. It's often used by programmers to describe a program in any programming language. Pseudocode is not a formal standard so it can sometimes be difficult to interpret. The pseudocode below shows the procedure for bubble sort:

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

Exercise

Write a swap function that swaps elements in an array and a vector. Start with the code below: 

#include <ArduinoSTL.h>

using namespace std; 

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

// Implement swap 
void swap(vector<string> &v, int pos) {
}

void loop() {
  vector<string> breakfast {"cereal", "eggs", "bacon", "toast", "juice"};

  
  cout << "Pre swap: " << breakfast << endl;
  swap(breakfast, 0);
  cout << "Post swap: " << breakfast << endl;
  
  delay(1000);
  
}

// Insertion operator for vectors operator<<()
// 
// This function allows you to use cout with a vector
// directly. Copy it into your project for this week 
// so that you will be able to better debug your code.
//
// @argument: ostream &os: A reference to the output stream to print to. 
// @argument: const vector<T> &v: A reference to a vector of ANY type. 
// @returns: The first parameter. 
// 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "vector: { "; 
  for (auto element : v) {
    os << element << " ";
  }
  os << "}";
  return os;
}

Requirements

  1. Save your sketch as swap.ino
  2. Your swap function should swap elements pos and pos+1
  3. Your swap function should check that pos+1 is a legal element in the vector 
  4. If you detect that pos+1 exceeds the bounds of the vector
    1. Print an error message
    2. Do not perform a swap 

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)
  • 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
Comments