Preview
Video Player
00:00
00:00
Sorting Lists
11:49We often need the items in a list to be in some order. Let's see how to sort a list.
Making searches faster isn't
the only reason to sort a list.
0:00
People can make more sense of information
when it's in some logical order.
0:04
This usually means sorting.
0:09
Let's learn how to sort a list.
0:11
If we want to sort the list
of names alphabetically,
0:14
we can just call the Sort
method on the list.
0:16
So we'll say students.Sort.
0:19
Now let's inspect this
student's list again.
0:24
This performs an in-place sort,
0:28
meaning the sorted items are stored
back in the list we called Sort on.
0:30
There are multiple sort algorithms.
0:35
Some sort algorithms work well for
small lists, others work well for
0:37
medium sized lists, and
others work best for large lists.
0:41
The Sort method picks
the best sort algorithm for
0:45
the size of the list,
we don't even need to think about it.
0:47
Numeric types like integer and
double have a natural sort order, so
0:50
calling Sort on a list of numbers
simply sorts them in ascending order.
0:54
How do you think the Sort method knows
how to sort a list of strings, though?
0:59
It might appear obvious if
the strings are all English and
1:03
they only contain letters A through Z.
1:07
But what if there are numbers or
other symbols in the string?
1:09
What if there are non-english
characters in it?
1:13
What should the sort order be then?
1:16
How can the Sort method know
how to sort any kind of object?
1:18
The truth is,
1:23
it can't, we need to tell the Sort method
how to sort the items in the list.
1:24
There are a few different ways to do this.
1:28
The reason the Sort method seems to
magically know how to sort various types
1:31
of objects is because they implement
the IComparable interface.
1:35
Let's take a look at the MSDN
documentation for the string type.
1:39
So let's search for System.String.
1:43
Here we see that it implements
both the IComparable and
1:51
IComparable of string interfaces.
1:55
Let's a take a look at the documentation
for the IComparable generic interface.
1:59
We want the generic version, so we want
the one that says IComparable(T) here.
2:07
Just like we can have generic classes like
list, we can also have generic interfaces.
2:12
We can see here that any class
that implements this interface
2:19
will have a method named CompareTo.
2:23
This method is used to compare
the object that the method is called on
2:26
with the item passed in.
2:30
This T here acts as a placeholder for
the actual type of object passed in.
2:32
Notice that CompareTo returns an integer.
2:39
CompareTo returns a negative number
2:43
if the object should be ordered
before the object passed in.
2:45
It returns a positive number if
the object should be ordered after
2:49
the object passed in.
2:52
And it returns zero if
the objects are equivalent.
2:54
Let's see what this looks like in code.
2:57
Let's create a new file and
name it Students.cs.
2:59
Here, we'll write a class to
hold details about students.
3:03
So we'll say, namespace Treehouse.
3:09
And then we'll name our class Student.
3:13
To make it so
it can be sorted inside of a list,
3:16
let's have it implement
the System.IComparible interface.
3:19
We needed to compare with other students.
3:26
So the type parameter here
we'll pass in is Student.
3:28
The thing we enter here between the angle
brackets is called the type parameter.
3:34
This is specifying that Student
can be compared with other objects
3:38
of type Student.
3:43
Now, inside the class,
let's have two properties.
3:44
Let's have string property
to hold the student's name.
3:48
So we'll say, public string Name,
with a getter and a setter.
3:51
We'll also have an integer that
holds the student's grade level.
4:00
Say public int GradeLevel.
4:04
This GradeGevel property will tell
us if they're in first, second, or
4:12
third grade, and so on.
4:15
Finally, let's implement
the IComparable interface.
4:19
For that,
we need to add the CompareTo method.
4:23
So we'll say, public int CompareToStudent.
4:26
And we'll call the student passed in,
that.
4:33
We'll have it first sort by the student's
name and then by grade level.
4:36
So I'll say int result =
4:41
this.Name.CompareTo(that.Name).
4:45
Notice that we can call CompareTo
on the properties of the class
4:52
because string also implements
the IComparable interface.
4:57
So if this.Name is the same as that.Name,
then the result will be equal to 0.
5:02
So we'll say if result = 0,
then we need to compare the grade levels.
5:10
So we'll say,
result = this.GradeLevel.CompareTo.
5:16
Int also has a CompareTo method because it
also implements the IComparable interface.
5:25
So we'll say CompareTo(that.GradeLevel).
5:29
Finally, we'll return the result
Let's exit out of the csharp REPL.
5:35
And let's compile this to make sure we
haven't introduced any compiler errors.
5:47
So we'll say mcs *.cs.
5:50
All right, looks pretty good.
5:55
Now, over in Program.cs,
we have our Main method.
5:57
Let's create a list of students and
then sort them.
6:02
So I'll say List<Student> and
6:06
call it students = new List<Student>.
6:10
And here we'll create three students.
6:15
So we'll say, new Student() { Name =,
say, "Sally".
6:17
GradeLevel is, she's in third grade.
6:28
And let's just copy this.
6:36
And change these, so I'll say this is Bob,
Also in third grade.
6:44
Let's put another Sally in second grade.
6:52
All right, };.
6:58
Now let's call sort on our student list.
7:01
So well say students.Sort().
7:05
Now let's print them out to
see how they've been sorted.
7:10
So we'll say foreach(Student
student in students),
7:13
Console.WriteLine.
7:22
And we'll use a format string,
so we'll type a $.
7:27
And then inside the curly braces here,
7:31
we'll say {student.Name} is in
7:36
grade {student.GradeLevel.}
7:41
All right, now let's compile this and
run it to see our sorted list of students.
7:50
We got some compiler errors here.
7:57
Looks like we forgot to put
System.Collections.Generic.
8:01
So let's put using
System.Collections.Generic,
8:05
can't forget our using directive.
8:11
We're getting this because we're
missing the using System namespace.
8:17
So we'll say, using System;, up here, too.
8:21
All right, now let's run our program.
8:28
So, do ls to see, okay,
we got program.exe.
8:31
We'll say mono Program.exe.
8:34
All right, we've got Bob is in grade 3,
Sally's in grade 2 and Sally's in grade 3.
8:39
We were able to sort objects
of type Student here
8:43
because we wrote the Student class.
8:47
So we got to decide how to
implement the CompareTo method.
8:49
Sometimes, we want to sort things that
we don't control the source code for.
8:53
So we can't make it implement the
IComparable interface like we did here.
8:57
Or sometimes we want
them ordered differently
9:01
than how the class says
they should be sorted.
9:04
In that case,
9:07
there are a couple other ways to tell
the list how to sort the objects.
9:08
Let's take a look at the documentation for
the List class.
9:12
So we can find that by searching for
9:16
System.Collections.Generic.List.
9:20
Here we go.
9:26
Let's search this page for the word Sort.
9:28
So I'll type in Sort.
9:32
And then we can jump down to the methods
by adding an open parenthesis here.
9:34
As you can see, there are four
overloads of the Sort method.
9:38
This first Sort method
will throw in an exception
9:42
if it's called on a list of objects that
don't implement the IComparable interface.
9:45
If we want to list the sort differently
than the way the object says it
9:50
should be sorted, or if the objects don't
implement the IComparable interface,
9:53
we can call one of these
other three methods here.
9:57
This one takes a special type
of object called a delegate.
10:00
A delegate is a function
that can be passed around
10:05
just like any other type of object.
10:07
Functions and
delegates can be called just like methods.
10:10
We'll learn more about
delegates in another course.
10:13
This is a generic delegate.
10:16
We can see that because it has a <T> here.
10:18
Essentially, the Sort method
can call this delegate and
10:23
pass it two objects that it wants to sort.
10:27
And the delegate returns an integer
just like the CompareTo method does.
10:29
This is actually how most people
call the Sort method, and
10:34
you'll see examples of how to
use this in other courses.
10:37
This third method here
takes an ICompare object.
10:40
Let's take a look at the documentation for
ICompare.
10:44
Again, we want the generic version here.
10:55
To tell the Sort method how to sort,
10:58
we can create a class that
implements the ICompare interface.
11:01
It has a single method and
it takes two parameters of the same type.
11:05
This type here is the generic
specified type parameter.
11:12
The compare method works just
like the CompareTo method
11:16
in the IComparable interface.
11:19
We can pass an instance of this object
to the Sort method, and it will call
11:21
the Compare method in order to determine
the order of the objects in the list.
11:25
We won't implement
the ICompare interface here.
11:29
Instead, I'm going to leave
this as an exercise for
11:32
you to practice implementing
generic interfaces.
11:35
You can refer back to the IComparerable
example we have back here in the Student
11:38
class.
11:43
Or you can also look down here at
the bottom of this page for an example.
11:43