Not all programs are created equal. In this course, we'll focus on writing quality code that runs correctly and efficiently. We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

Loading...

来自 University of Toronto 的课程

学习编程：撰写高质量代码

311 个评分

Not all programs are created equal. In this course, we'll focus on writing quality code that runs correctly and efficiently. We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

- Jennifer CampbellAssociate Professor, Teaching Stream

Department of Computer Science - Paul GriesAssociate Professor, Teaching Stream

Department of Computer Science

You'll now learn about another algorithm for sorting objects from smallest to

largest. This one is called selection sort, we use

this example list. We use i to mark the index of the first

position in the unsorted part of the list.

And initially the entire list is unsorted.

Next, we need to find the index of the smallest item in the unsorted part of the

list. And swap it with the item at index i.

Let's pass over the items of the list, keeping track of the smallest one.

Three is the smallest I've seen so far. Three is still the smallest.

Now 2 is the smallest, and 2 is still the smallest, so when I reach the end of the

list, I find that the smallest item was the 1 at index 2.

Now, I'll swap the item at index i with the 1 at index 2.

We've now completed the first pass. It's time to start the second pass, there

are now two parts of the list. A sorted part and an unsorted part, index

i represents the index of the first item in the unsorted part of the list.

Like before, we pass over the items in the unsorted part of the list, looking

for the smallest, 7 is the smallest I've seen so far.

Now 3 is the smallest, and 3 is still the smallest.

So we swap the value at position two, three, with the one at position i.

Next, it's time for the third pass. After passing over the items in the

unsorted part of the list, we find that 5 is the smallest.

And we swap it with the item at index i. On the last pass, there's only one item

left in the unsorted part, and the list is sorted.

To summarize, at the beginning, the entire list is unsorted and index i is

equal to 0. After some passes have been completed,

there are two parts of the list, a sorted part and unsorted part i represents the

index of the first item in the unsorted part of the list.

At the end the entire list is sorted and i is equal to the length of the list.

Let's implement this algorithm. As we saw in the example, we complete

length of the list number of passes through this algorithm.

During each pass, we find the index of the smallest item in the unsorted part of

the list. That is the list from index I to the end,

and we swap the smallest item with the one on index i to determine the index of

the smallest we'll use the helping function named get_index_of_smallest that

we'll write in a moment. Once we know the index of the smalest

item we swap the item of that index with the item at index i.

Next, let's implement that helping function.

We'll use a variable to keep track of the index of the smallest item that we've

seen so far. At the beginning of a pass, the smallest

item that we've so far will be at index i.

We then pass over the rest of the items in the unsorted particle list, comparing

each one to the smallest we've seen so far.

If we find something smaller, we update index to smallest to refer to the index

of that value. Once the loop has completed, we return

the index of the smallest item from the unsorted part of the list.

Let's from the dock tests. Everything passes and we're done.