The Self-Taught Computer Scientist

Introduction to Algorithms
54
Python’s other function for sorting is 
sort
, which has the same optional parameters as 
sorted
, but 
unlike 
sorted
, 
sort
works only on lists. Also, unlike 
sorted
, 
sort
sorts in place: it changes the original 
list instead of returning a new one. Here is an example of using 
sort
on a list:
a_list = [1, 8, 10, 33, 4, 103]
a_list.sort()
print(a_list)
>> [1, 4, 8, 10, 33, 103]
As you can see, Python sorted the numbers in your original list in ascending order.
Vocabulary
sorting data: Arranging data in a meaningful way.
bubble sort: A sorting algorithm where you iterate through a list of numbers, compare each number 
with the next number, and swap them if they are out of order.
stable sort: A sort that does not disturb any sequences other than the one specified by the sort key.
insertion sort: A sorting algorithm where you sort data like you sort a deck of cards.
merge sort: A recursive sorting algorithm that continually splits a list in half until there are one or 
more lists containing one item, and then puts them back together in the correct order.
divide- and- conquer algorithm: An algorithm that recursively breaks a problem into two or more 
related subproblems until they are simple enough to solve easily.
hybrid sorting algorithm: An algorithm that combines two or more other algorithms that solve the 
same problem, either choosing one (depending on the data) or switching between them throughout 
the algorithm.
Challenge
1. 
Research and write a sorting algorithm that is not a bubble sort, insertion sort, or merge sort.

---

5
String Algorithms
One of the most important skills any entrepreneur should learn is to program a computer. This is a 
critical skill if you want to start a tech startup, but a basic knowledge of code is useful even in tradi-
tional fields, because software is changing everything.
Redi Hoffman
In this chapter, you will learn how to solve some of the most common string- based technical inter-
view questions. While you most likely won’t have to find anagrams at your software engineering job, 
learning how to detect them teaches you to solve problems using concepts such as sorting, which you 
will have to do. Furthermore, other things you will learn in this chapter, such as modular arithmetic 
and list comprehensions, will be useful in your day- to- day programming.
Anagram Detection
Two strings are anagrams if they contain the same letters, but not necessarily in the same order (case 
does not matter). For example, 
Car and arc are anagrams. The key to determining whether two strings 
are anagrams is to sort them. If the sorted strings are the same, they are anagrams. Here is how to write 
an algorithm that determines whether two strings are anagrams:
def is_anagram(s1, s2):
s1 = s1.replace(' ','').lower()
s2 = s2.replace(' ','').lower()
if sorted(s1) == sorted(s2):
return True
else:
return False
s1 = 'Emperor Octavian'
s2 = 'Captain over Rome'
print(is_anagram(s1,s2))
>> True

---