Find It and Put It in Order

Name: Find It and Put It in Order
Author: StemPy Lab

Finding things and putting them in order are the two most common jobs in computing. A phone finds a contact among thousands, and a website lists the cheapest items first. In this course you search a list item by item and then by halving it, you see why the second way is so much faster, and you sort lists with Python's tools and with small sorting methods that you write yourself. A lesson on counting the work shows how to compare methods by the number of steps they need, and why the answer matters when the list grows. A class ranking with ties is the project at the end. The practice runs your code on many lists and tells you which results are wrong.

5 lessons, about 2 h 30 min5 simulations13 problems10 practice questionsPython in every lesson

Created by StemPy Lab

Course outline (5 lessons)

Lesson 1about 30 min
Linear search
Linear search looks at the items one by one from the start until it finds the target. It works on any list, in order or not. A search function usually gives back the position, and minus one when the target is not there. In the worst case, when the target is last or missing, it checks every item, so n items need n checks. The method index and the word in search a list for you. The same loop can find all the positions of a target, or the first item that passes a test.
1 simulation2 practice questions3 Python programs3 problems1 Python lab1 question set
Read the lesson
Lesson 2about 30 min
Binary search
Binary search needs a list that is already in order. It looks at the middle item, and throws away the half that cannot hold the target, then repeats on what is left, so each check halves the list. It uses a low and a high position and a while loop that continues while low is not more than high. A million items need at most about 20 checks, against a million for linear search. The price is that the list must be sorted first, and on a list that is not in order, binary search gives wrong answers with no message.
1 simulation2 practice questions2 Python programs2 problems2 Python labs
Read the lesson
Lesson 3about 35 min
Sorting
sorted gives a new sorted list and sort changes the list itself and gives back None. reverse equals True puts the biggest first, and key changes how the items are compared, for example key equals len for the length, or key equals str.lower to ignore capital letters. Tuples are compared item by item, so a list of pairs sorts by the first item, and a key function can sort by the second or by two things at once. Python's sort is stable, so equal items keep their old order. Bubble sort and selection sort are two simple methods that you can write yourself: they are slow for long lists, but easy to understand.
1 simulation2 practice questions4 Python programs6 problems2 Python labs
Read the lesson
Lesson 4about 30 min
How fast is it? Counting the work
To compare methods, count the work: the number of checks or comparisons they need, as a function of the length n of the list. Linear search needs n checks in the worst case, binary search needs about the number of times that n can be halved, and bubble sort needs n times n minus one over two comparisons, so doubling the list makes the sort four times slower. A method whose work grows slowly is better when the list is long, and the difference is huge for a million items. Counting is better than timing, because it does not depend on the computer. For a short list the difference does not matter, and a simple method is the right choice.
1 simulation2 practice questions2 Python programs1 problem1 Python lab
Read the lesson
Lesson 5about 25 min
Project: a class ranking
In this project we rank a class. The students are pairs of a name and a mark, and the ranking sorts by mark with the biggest first, and by name for equal marks, using a key that is a tuple. Ties get the same rank, and the next rank is skipped, as in a race. The program also shows the top three and uses binary search on the sorted marks to ask whether a mark is there. We plan the table of expected ranks by hand, build the program in steps, test the ties and the edges, and extend the ranking with a search by name and a median.
1 simulation2 practice questions1 Python program1 problem1 Python lab
Read the lesson

Test Your Learning

Searching and Sorting: Predict the Output

10 questions · 15 min

Not started

Your teacher

StemPy Lab

← All Courses

← PreviousA Function That Calls Itself →

More onPython Essentials › Searching and Sorting

Discussion (0)

Loading…

Find It and Put It in Order

Course outline (5 lessons)

Linear search

Binary search

Sorting

How fast is it? Counting the work

Project: a class ranking

Test Your Learning

Your teacher

Discussion (0)