Sorting and Searching3:55 with Jay McGavren
To help further your understanding of algorithms, this course is going to look at two categories: sorting algorithms and searching algorithms. You could argue these are the easiest kinds of algorithms to learn. But in learning how these algorithms are designed, we'll cover useful concepts like "recursion" and "divide and conquer" that are used in many other sorts of algorithms, and can even be used to create brand new ones.
[MUSIC] 0:00 You may have heard that algorithms and computer science are boring or 0:09 frustrating. 0:12 They certainly can be hard to figure out, 0:13 especially the way some textbooks explain them. 0:15 But once you understand what's going on, algorithms can seem fascinating, 0:18 clever, or even magical. 0:22 To help further your understanding of algorithms, this course is 0:24 going to look at two categories, sorting algorithms and searching algorithms. 0:27 You could argue that these are the easiest kinds of algorithms to learn. 0:32 But in learning how these algorithms are designed, 0:36 we'll cover useful concepts like recursion and divide and conquer that are used in 0:38 many other sorts of algorithms, and could even be used to create brand-new ones. 0:42 By the way, all the codes sample I'm going to show in the videos will be in Python, 0:47 because it's a popular language that's relatively easy to read. 0:51 But you don't need to know Python to benefit from this course. 0:54 You can see the teachers notes for each video. 0:57 For info on implementing these algorithms in your own favorite language. 0:59 Our goal with this course is to give you an overview of how sorting and 1:03 searching algorithms work. 1:07 But many algorithms have details that can be handled in different ways. 1:08 Some of these details may distract from the big picture, so 1:12 we've put them in the teacher's notes instead. 1:15 You don’t need to worry about these when completing the course for the first time. 1:17 But if you’re going back and 1:21 referring to it later, be sure to check the teacher's notes for additional info. 1:22 Suppose we have a list of names, it’s a pretty big list, 100,000 names long. 1:26 This list could be part of an address book or social media app. 1:31 And we need to find the locations of individual names within the list, 1:34 possibly to look up additional data that's connected to the name. 1:38 Let's assume, there's no existing function in our programming language to do this, or 1:41 that the existing function doesn't suit our purpose in some way. 1:46 For an unsorted list, 1:49 our only option may be to use linear search, also known as sequential search. 1:50 Linear search is covered in more detail elsewhere on our site, 1:55 check the teacher's notes for a link if you want more details. 1:58 You start at the first element, 2:02 you compare it to the value you're searching for. 2:03 If it's a match, you return it, if not, you go to the next element. 2:05 You compare that to your target. 2:10 If it's a match, you return it, if not, you go to the next element, and 2:11 so on through the whole list. 2:15 The problem with this is that you have to search the entire list every single time. 2:18 We're not doing anything to narrow down the search each time. 2:23 We have to search all of it. 2:25 If you're searching a big list or 2:28 searching it repeatedly, this amount of time can slow your whole lab down, 2:29 to the point that people may not want to use it any more. 2:33 That's why it's much more common to use a different algorithm for searching lists, 2:36 binary search. 2:41 Binary search is also covered in more detail elsewhere on our site. 2:41 Check the teacher's notes for a link. 2:45 Binary search does narrow the search down for us. 2:48 Specifically, it lets us get rid of half the remaining items we need to search 2:50 through each time. 2:55 It does this by requiring that the list of values be sorted. 2:56 It looks at the value in the middle of the list. 3:01 If the value it finds is greater than the target value, 3:04 it ignores all values after the value it's looking at. 3:06 If the value it finds is less than the target value, 3:09 it ignores all values before the value it's looking at,. 3:12 Then it takes the set of values that remain and 3:15 looks at the value in the middle of that list. 3:17 Again, if the value it finds is greater than the target value, 3:20 it ignores all values after the value it's looking at. 3:23 If the value it finds is less than the target value, 3:26 it ignores all values before the value it's looking at. 3:28 But as mentioned, 3:32 binary search requires the list of values you're searching through to be sorted. 3:33 If the list weren't sorted, you would have no idea which half of the values 3:37 to ignore, because either half could contain the value you're looking for. 3:41 You'd have no choice but to use linear search. 3:45 So before we can use binary search on a list, 3:48 we need to be able to sort that list. 3:50 We'll look at how to do that next. 3:52
You need to sign up for Treehouse in order to download course files.Sign up