EBoard 38: Sorting (Section 1)

Warning! You are being recorded and transcribed, provided the technology is working correctly.

Approximate optimistic overview

  • Administrivia
  • Questions and answers
  • Background: What is computer science?
  • The problem of sorting
  • Designing sorting algorithms
  • Turning design into code (if time)

Administrative stuff

Introductory notes

  • As you can tell, today is a talk day, not a lab day.
  • Happy Cinco de Mayo!
  • Happy Penultimate Week! (At least for students.)
  • Congratulations to our baseballers who made it to the playoffs! (Also tennisers, trackers and fielders, ping-pongers, and others I’ve missed.)
  • Please plan to attend class Wednesday for project presentations.
    • There will be fruit.
    • Missing class without a good reason: Five tokens
  • Please plan to attend class Friday for wrapup activities.
    • If you are unable to make it to class on Friday (e.g., because your team is traveling), please plan to come early on Wednesday (Section 1) or stay late on Wednesday (Sections 2 and 3).
    • Missing class without a good reason: Five tokens
  • This is my last week of bookable office hours. I’ll be available by appointment during finals week.
  • If you took the most recent diagramming structures quiz, you should have received an email message from Gradescope at about 9pm on May 1 entitled [CSC-151] The “last” diagraming structures quiz. You should read that email message. Let me know if you didn’t receive it.

Upcoming activities

Scholarly

Artistic

  • Any day it’s open. GCMoA. BAX
  • Thursday, 8 May 2025, 7:30–10:00 p.m., Sebring-Lewis. Symphonic Band Concert

Multicultural

  • Monday, 5 May 2025, 4pm, Global Living Room. Japanese Student Association Matcha Latte Event!

Peer

Musical, theatric, sporting, and academic events involving this section’s students are welcome.

  • Read articles by your fellow CSC-151 students and comment on them online. This is the last week of any S&B articles!

Wellness

  • When and where they usually occur. Badminton Club, Brazilian Jiu-Jitsu, _HIIT Training, Nerf at Noyce, Yoga.
  • Thursday, 8 May 2025. 4:30–6:30 p.m., Off Campus. Forest Bathing.
    • Sign ups are required.
  • Tuesday, 13 May 2025, 5:00–6:00 p.m., HSSC Atrium. Therapy Dogs.
  • Tuesday, 13 May 2025, 7:15–8:15 p.m., HSSC Atrium. Therapy Dogs.

Misc

  • Wednesday, 7 May 2025, Noon–1:00 p.m., HSSC A2231 (Auditorium) Community Forum
    • “Weekly discussion on legal protections and recourse on issues that higher education and Grinnell College face.”
    • Also online.
    • Surviving the summer.
  • Sunday, 11 May 2025, 7:30–8:30 p.m., Science 3819. Mentor Session: SoLA 5

Other good things

These do not earn tokens, but are worth your consideration.

Upcoming work

Questions

Administrative

I’ve missed way too many reading responses, labs, and/or metacognitive reflections. Can you just waive the penalty for missing those things?

Each of these is important to your learning in its own way.

Reading responses ensure that you’re ready for the lab. At least they are supposed to.

Metacognitive reflections help you develop as a learner.

Labs help you learn the material. They may even be the primary way in which you learn the material.

I will, however, cap the grade decrease at one letter grade provided (a) you turn in the post-reflection for MP9, (b) you turn in the post-reflection for SoLA 4, (c) set up an appointment with academic advising to discuss strategies for getting regular work done on time, and (d) send me a message describing one or two strategies you’ve decided upon.

Also: I will not be charging tokens for late reading responses, lab writeups, or metacognitive reflections.

I won’t be in class on Friday. What should I do?

If you are unable to make it to class on Friday (e.g., because your team is traveling), please plan to come early on Wednesday (Section 1) or stay late on Wednesday (Sections 2 and 3).

Does only one team member submit the MP9?

Yes, only one member should submit MP9.

Background: What is computer science?

TPS

Snarky answer: “The Science Behind Computing”

A technique for better understanding the world.

Asking and answering questions.

A mechanism for understanding the world based on observation, hypothesis generation, experiment design, experimentation, analysis, and hypotheseis revision.

Perhaps our hypothesis is “My code will work”. It’s usually an incorrect hypothesis.

Another suggestion: Solving problems by writing algorithms and data structures (ways of organizing information). [Good answer]

What problems do we solve? Usually ones that come up in the process of doing work. We also look to generalized problems.

One typical problem: Finding information. We can arrange the information in a dictionary, which makes it fast to find. We can just put in a list and use linear search, we can put it in a vector (ordered by something) and use binary search.

If we want our data ordered for binary search, we need a way to order information (“sort” - to put in order).

Typical running times

  • Constant time: Independent of the size of the input
  • Logarithmic: Goes up by a constant amount each time you double the size of the input.
  • Linear: Doubles each time you double the size of the input.
  • Quadratic: Quadruples every time you double the size of the input.
  • Exponential: Approximately doubles every time you add another element.

The problem of sorting

Given a collection (list, vector) of values and a mechanism for comparing values (e.g., <=, string<=?, char<=?), put the values in order from smallest to largest (or largest to smallst).

Designing sorting algorithms

TPS: Design a sorting algorithm

Inputs: A list or vector of values + a way to compare any two values

Output: The same group of values, now in order. (for lists, we’ll output a new list; for vectors, we’ll change them in place)

English instructions are fine. We’ll try to be sensible about interpreting your instructions.

Algorithm 1: Put things from smallest to biggest (Selection Sort)

  • Find the smallest in the list
  • Put it at the front (cons (smallest lst less-than?) ...)
  • Remove it from the list.
  • Repeat/Recurse

How do we find the smallest?

  • Grab the first element.
  • Compre to the next.
  • Grab the smaller of the two.
  • Keep going.

Is selection sort linear, quadratic, worse?

  • Smallest is linear
  • If we had 9 things in the list, we’d do 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 steps, which is 45.
  • If we had 18 things in the list, we’d do 18 + 17 + … + 1 = 171.
  • This algorithm is quadratic.

Algorithm 2 (Bubble Sort, Sam’s least favorite sorting algorithm)

Sub algorithm

  • Compare the first two elements
  • If they are in the wrong order, switch them.
  • Next do the second and third.
  • Keep doing that until you get to the end.
  • After one round of the sub algorithm, the largest is at the end.

Repeat the sub-algorithm on smaller and smaller sections until everything is sorted.

“Worse than quadratic.” WRONG

The sub algorithm is linear.

We run the sub algorithm n times. n times n = n squared.

Divide and conquer (general)

  • Break the list into two parts (based on what criteria?)
  • Sort each half
  • Combine together (how?)

Divide and conquer option one

  • Find the average of the values
  • Divide into those things < the average, = the average, > average
  • Sort the smaller and larger things
  • You can just put them next to each other.

Example

  • 6, 1, 4, 7, 8, 2, 9
  • Average is about 5.3
  • Less: 1, 4, 2
  • Greater: 6, 7, 8, 9
  • Magically sort
  • Less sorted: 1, 2, 4
  • Greater: 6, 7, 8, 9
  • Plug together: 1, 2, 4, 6, 7, 8, 9

Another example

  • 100,000, 1, 10,000, 100, 1,000, 1,000,000, 10
  • Average is 158,000
  • Smaller: 100,000, 1, 10,000, 100, 1,000, 10
  • Larger: 1,000,000

Hmmm

  • Let’s try this with smaller.
  • Average is about 20,000
  • Smaller: 1, 10,000, 100, 1,000, 10
  • Larger: 100,000

Hmmm

We are splitting into one thing and n-1 things. So this won’t be any better than our previous sorts. At least not for this example.

If we split at the median rather than average, th two halves will be approximately equal in size. (Finding the median is hard.)

Implementing sorting algorithms

TPS: Selection Sort

  • Find the smallest in the list
  • Put it at the front (cons (smallest lst less-than?) ...)
  • Remove it from the list.
  • Repeat/Recurse

You’ll need to implement

  • (smallest lst less-equal?)
  • (remove val lst)
  • (selection-sort lst less-equal?)
(define smallest
  (lambda (lst less-equal?)
    (reduce (lambda (x y) (if (less-equal? x y) x y))
            lst)))

remove is already defined.

(define selection-sort
  (lambda (lst less-equal?)
    (if (null? lst)
        null
        (let ([s (smallest lst less-equal?)])
          (cons s
                (selection-sort (remove s lst) less-equal?))))))

Copyright © Eric Autry, Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Nicole Eikmeier, Fahmida Hamid, Priscilla Jiménez, Barbara Johnson, Titus Klinge, Peter-Michael Osera, Leah Perlmutter, Samuel A. Rebelsky, John David Stone, Anya Vostinar, Henry Walker, and Jerod Weinman.

Unless specified otherwise elsewhere on this page, this work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.