0:01

The two of the most important problems that we deal with on a regular basis, and

Â that are solved, solvable computationally in a very nice way,

Â are the sorting problem and the searching problem.

Â When you go a university and you ask for your, for your record, the, the,

Â the person who's giving you your records is going to be doing a search for

Â your records.

Â And usually, they search for your records, based on your name, for

Â example or based on your student ID, or based on your social security number.

Â So, there, there is need always for these algorithms that will search.

Â When you look up, the, the phone number of someone, you also are searching for

Â a phone number in a very long list of numbers.

Â When when we are looking up a word in a dictionary, we are also doing some search.

Â And, the same thing with sorting.

Â That when we do, when we for example do a certain task, and

Â we have lots of results returned, we would like them to be sorted in a certain way.

Â For us when we teach a course, and

Â at the end of the semester we are assigning the grades.

Â The letter grades in the course for example.

Â We would like to sort the grades by the grade of the student.

Â And then we draw some cutoffs there and

Â decide on which grades, which students get a, which students get b, and so on.

Â These are two very fundamental problems that, that arise in many applications.

Â Even though sometimes they are not really, what you see.

Â So you're looking at certain application, like again when you look at,

Â at a system that is managing the students' records,

Â the first thing that comes to mind is not sorting or searching there.

Â You have a system that you can query it for, for sorting questions.

Â However, underlying the hood of such systems.

Â There is some sorting mechanism, there is some searching mechanism, that allows

Â the user, again to search that, that that system for a specific record.

Â Or sort that system, because of certain statistics for example.

Â Again, we want to sort grades so that we can, we can decide on the,

Â on the letter grades or the distribution on grades in a course.

Â 2:11

These problems are very well defined.

Â In the sense that we are usually dealing with a list of numbers or

Â strings of certain entities that we would like to sort them.

Â So I'm going to talk first about sorting, and then we will go to searching.

Â And, the first question is what, what do we mean by sorting?

Â Okay.

Â When we talk about sorting in this context, or in the context of algorithm,

Â it means that we would like to place the items in a, in a, in a list.

Â In a way that we, that they are ordered, such that for example, if I'm talking

Â about, increasing order, I want the first item to be the smallest, the second item

Â to be the second smallest, the third item to be the third smallest, and so on.

Â It is not sorting in the sense that,

Â we would like to put all items of a certain type in a bin, okay.

Â We would like to sort them so that, again, the, they are in a certain order.

Â 3:02

When we talk about that, the question is, the first thing that comes to

Â mind among students especially, they think always about numbers.

Â We are sorting a list of numbers.

Â So is sorting limited to numbers?

Â The answer is no.

Â Again, if you look, if you look at the dictionary and I know that

Â today nobody uses an actual dictionary and you usually look up the word online.

Â But in the good old days there was, used to be a big volume that's

Â called dictionary and you look up a word in that, in that volume.

Â And if you look at the words, how they are arranged in that dictionary,

Â they are arranged in a certain order, right?

Â So all the words that start with a are first.

Â All the so, words that start with b are second.

Â All the words the start with c are third.

Â But also within that categorization there is still order.

Â First we start with the shortest word that starts with a,

Â and then the second shortest, and so on.

Â 3:53

So, we can order numbers, we can order strings.

Â Can we order something else?

Â Can we, do we sort anything else?

Â And the answer is yes, you can sort any list of items,

Â as long as there is some sort of order defined on this items.

Â What's so special about numbers or strings?

Â What's nice about numbers is that if I, you give me any two numbers I

Â can compare them and I can tell you this number is smaller than that.

Â Or, if you give me two numbers a and b, we have one of three options,

Â either a is smaller than b, or a is greater than b, or a equals b.

Â When we have a set like this a set of numbers,

Â such that every two items are comparable, I can compare them and

Â say which one is smaller than the other, or if they're equal.

Â We have something we call total order, tha,

Â in the sense that I can compare every two elements in that set and make a, a,

Â a statement about which one is smaller or equal.

Â 4:48

Some, if we have a set of items or

Â a collection of items, and we have a total order defined on them, we can do sorting.

Â This is why we can sort strings.

Â If you give me a collection of strings, I can put them in a certain order.

Â Again, I can put them based on which one starts with a, which one starts with b,

Â which one starts with c.

Â Then, within all that start with a, I can decide that, based on the second letter,

Â which one starts with a, b, c, and so on.

Â Or I can sort them based on length.

Â First all the words that start with a and of length 1.

Â Then all the words that start a and of length 2.

Â Then all the words that start with a and of length 3 and so on.

Â So if you think about it,

Â of all the words that start with a of length 1, there is one.

Â 5:33

Then of all the words that start with a and there are two of them.

Â There is, if, of length, it starts with a and

Â of length 2, that is aa, ab, ac, az.

Â Then we can think about all the words that start with a of length 3.

Â They are aaa, aab, aac and so on.

Â Notice how I am ordering here.

Â I'm saying, first, we have this.

Â Here are all of them that are of length 1, here are all the words of length 2,

Â here are all the words of length 3.

Â Within each category, when I say of or, of, of, of length 2,

Â I look at the second letter and I order them by the contents, so the,

Â all the ones that the second letter is a then b then c and then z.

Â Here when we do 3, it's the same thing.

Â The, all of the, the first, first we list all of the ones that start,

Â the second letter is a, and then based on the third one, a, b, c, and so on.

Â This is known as lexicographical order.

Â This is known as the lexicographical order, okay.

Â Now, this, the reason that we can,

Â we can sort strings, like this, is because we have, we can define this.

Â So now I can say that a is, for example, smaller than aaa.

Â I know this because, based on this order,

Â I'm saying that this is first, this is second, this is third, this is fourth.

Â So I am using, I can use this notion of a is smaller than aaa.

Â Okay.

Â Of course, you are not used to seeing this is smaller than this, okay.

Â But think about it, it precedes it.

Â This precedes this in that order, right.

Â Or I can say that ac > ab, because ac falls after ab, right.

Â Of course az = az, right?

Â So if you give me any string, over the English alphabet for example.

Â I can sort them like this.

Â And for every pair of them, I can tell you if, if for every pair of strings x and y.

Â I can tell if you if x is smaller than y, if y is smaller than x or

Â if x equals y, okay.

Â So this is what it means to have a collection of items, and

Â have total order on them so that I can really compare.

Â The, the, the other, the other definition that's not

Â total order we sometimes define something that's called partial order.

Â Partial order is,

Â is when we have a situation where I have a collection of items.

Â For some pairs of the items I can compare them, I can tell you x is smaller than y.

Â For some pairs of items, for example,

Â I have no notion which one comes before the other, okay.

Â One example of partial order arises, for

Â example, when we talk about subsets, or sets.

Â 8:15

So if you have a collection of sets, so here, our, our, set of items is strength.

Â It's easy to think about it when we talk about integers.

Â 1, 3, 7, 9, 100, 5, million,

Â for any item here, I can look at it and tell you whether, you know,

Â which one is smaller than the other so I can sort them, I can put them in an order.

Â In this case it's going to be 1, 3, 5, 7, 9, 100, and then million, okay.

Â It's very simple, right, I can take this, and then put them there.

Â If you give me strings, I can order them like this.

Â Now, let's look at a different type of data.

Â Suppose I give you sets.

Â [SOUND] Suppose I

Â have these six

Â 9:12

sets here.

Â These six sets, can I order them?

Â Can I say which one is smaller than the other or which one comes before the other.

Â The answer is yes for some of them, the answer is no for some, for others.

Â So one, the, the natural way to order sets like these, is to think about containment.

Â Which one contains the other?

Â So, if I look at these here, I say that for

Â example, a, b is a subset of a, b, c, right.

Â A is a subset of a, b, c, it is a subset of a, b, right.

Â 9:49

The empty set is a subset of any set.

Â Empty set is subset of these.

Â B, c is a subset of this, right.

Â bd, bd is not a subset of b,c, it is not a subset of empty set.

Â It is not a subset of this, it is not a subset of this,

Â it is not a subset of this.

Â So if you give me these two sets for example, b,c and bd,

Â I cannot give an order on this, I cannot say b,c is smaller than bd.

Â 10:18

I cannot say b,d is smaller than b,c.

Â I cannot say, they, they are definitely not equal.

Â So this is a case of a collection of items,

Â where we don't really have a total order, we have partial order.

Â Again, what does it mean, partial order?

Â For some pairs of them I can tell you which one is smaller, or

Â which one precedes the other.

Â But for some pairs, like, these, I cannot tell you anything about them.

Â I don't, I cannot say that this one is smaller than this.

Â This one is smaller than this.

Â Of course, I can define an arbitrary order on this.

Â I can decide, that this is smaller than this.

Â This is smaller than this.

Â This is smaller than this.

Â This is smaller than this.

Â This is smaller than this.

Â But, if you look at this, it is an order, I defined an order,

Â I force them to be ordered like this, but does this make sense?

Â 11:13

here, they are, these are natural orders, this is natural order, okay.

Â So, when we talk about sorting, we have a collection of items, a list of items.

Â We have, we know they are orderable, they can be ordered.

Â And the question is that we want to, we want to answer is, how do we sort them?

Â The sorting problem again,

Â now we can define it as, I have a list of items that are orderable.

Â I want to order them,

Â I want to sort them in such a way, that the first item is smaller than the second,

Â second smaller than the third, third smaller than the fourth and so on, okay.

Â This is the sorting problem.

Â