Search and sort: finding and ordering data
Computers search and sort all the time. A search algorithm looks for an item: you look through a class list for a name, or along a shelf for a book, and you stop when you find it. The simple program below looks at every number of a list (Week 7 explains lists) and remembers whether it met 10. A sorting algorithm puts items in order, ascending: numbers from small to large, names from A to Z. Python has two ways: sorted(numbers) gives a new sorted list and leaves numbers as it was, but numbers.sort() changes the list itself. You can also sort by hand. Compare neighbours and swap them if the left one is larger; after enough rounds the list is in order.
1numbers = [4, 10, 7] 2found = False 3for n in numbers: 4 if n == 10: 5 found = True 6if found: 7 print("Found") 8else: 9 print("Not found")
Found
1numbers = [4, 10, 7] 2found = False 3for n in numbers: 4 if n == 5: 5 found = True 6if found: 7 print("Found") 8else: 9 print("Not found")
Not found
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | Step | 1st | 2nd | 3rd | 4th |
| 2 | start | 5 | 2 | 8 | 1 |
| 3 | after round 1 | 2 | 5 | 1 | 8 |
| 4 | after round 2 | 2 | 1 | 5 | 8 |
| 5 | after round 3 | 1 | 2 | 5 | 8 |
Write a list of five names of your own on paper and sort them from A to Z by hand, comparing neighbours. Then search for one name and count how many items you looked at before you found it.