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...

From the course by University of Toronto

Learn to Program: Crafting Quality Code

280 ratings

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

One approach to solving the sorting problem is to use the insertion sort

Â algorithm. That's what this lecture is all about.

Â We call from selection sort, the state of the list at the beginning after some

Â passes, and at the end. The same is true for insertion sort.

Â At the beginning, the entire list is unsorted and i refers to zero.

Â After some passes have been completed, part of the list is sorted and part is

Â not. I refers to the index of the first item

Â in the unsorted part of the list. At the end, the entire list is sorted,

Â and i refers to the length of the list. For insertion sort, one pass at the

Â algorithm involved taking the item at index i and including it in the sorted

Â section of the list. Let's look at an example.

Â Since the entire list is still unsorted, adding i to the sorted part of the list

Â is simple. We just increment i and move on to the

Â next pass. The 7 is compared with the 3, and since 7

Â is greater than 3, it's in its correct position.

Â Next, the two needs to be include din the sorted part of the list.

Â We know that the 5 will be in the same position as it was before.

Â In any given pass, only the items from index zero up to and including index i,

Â might change. 2 is less than seven, and it's less than

Â three, so the two belongs at index zero. The 7 will be removed over one position,

Â and the three will be moved over a position, making room to put the two at

Â index zero. Now let's try for the fourth pass.

Â The element index I the fourth path, the element index by five needs to be

Â included in the sorted parts lists. 5 is less than 7 and it's greater than 3,

Â so the 7 shifted to the right in the 5 is inserted at index 2.

Â Let's implement this algorithm. For each pass through the algorithm the

Â item at index i is inserted into the sorted part of the list.

Â The insert function is a helper function that we'll now write.

Â The variable value will refer to the list at index i, which is the item to be

Â inserted into the sorted cards list. Next, we need to find the index j, where

Â the value belongs. We also need to make room for the value

Â by shifting. And once we know the index where the

Â value belongs, index j, we need to put the value there.

Â Finding the index and making the room is the trickiest bit.

Â For now, we'll leave the y loop condition unspecified and we'll add it in a moment.

Â In the body of the loop, one item will be shifted to its right, the index j, is

Â then decreased by 1. To determine the loop condition, let's

Â revisit our example. Initially, j refers to i, 2 is compared

Â with 7, and because it's less than 7, the 7 will be shifted to the right.

Â Then the value of j will be decreased. Next, 2 is compared with 3, and the 3 is

Â shifted to the right, then the value of j is decreased again.

Â At this point j refers to zero, it's not possible to go any further to the left.

Â We've found the location where the two belongs.

Â Let's add this reason for stopping to the [UNKNOWN] loop condition.

Â We want to stop when j is equal to zero, so we'd like to continue as long as it's

Â not. There's another reason why the loop might

Â end as well. Let's consider a second example.

Â In this case, 5 is compared with 7, and 7 is shifted to the right.

Â The value of J is decreased. Next 5 is compared with 3, and because

Â it's bigger than 3 we stop. We stop when the list at j minus 1 is

Â less than or equal to the value, so the second condition under which our wild

Â loop should continue is that l at j minus 1 is greater than the value.

Â Now, that we've finished the implementation, let's run the doc test.

Â The test passed.

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