Loading...

The sorting problem

Course video 2 of 21

Sorting, searching, big-O notation, the Master Theorem

Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems. In part 2 of this course, we will study advanced algorithmic techniques such as divide-and-conquer and dynamic programming. As the central part of the course, students will implement several algorithms in Python that incorporate these techniques and then use these algorithms to analyze two large real-world data sets. The main focus of these tasks is to understand interaction between the algorithms and the structure of the data sets being analyzed by these algorithms. Once students have completed this class, they will have both the mathematical and programming skills to analyze, design, and program solutions to a wide range of computational problems. While this class will use Python as its vehicle of choice to practice Algorithmic Thinking, the concepts that you will learn in this class transcend any particular programming language.

Skills You'll Learn

Algorithms, Python Programming, Algorithmic Efficiency, Dynamic Programming

Taught By

Luay Nakhleh
Associate Professor
Scott Rixner
Professor
Joe Warren
Professor

Transcript

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.

So, how do we do searching and how do we do sorting, in, in, in practice?

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.

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.

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.

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.

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.

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

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.

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.

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?

The answer, I don't think so.

Right? I we, I can define this, but

it's not a natural order, it's not a meaningful order, right.

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.

About Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play