Interview Prep: Insertion Sort

4.0 Average Customer Rating

Brush up on this algorithm that is sometimes asked about in interviews

  • 8 Videos
  • 0 hours 23 minutes
  • 60 Happy Students

About the course

Description

Insertion sort is a commonly taught algorithm, and some interviewers like to ask about it. As you’ll see in this class, it’s an easy algorithm to understand and implement. You’ll learn the algorithmic complexity and understand why the algorithm is rarely used.

I’ll give a walkthrough of the source code, which I also provide in my repository: github.com

Also watch my course on Binary Search, insertion sort makes use of that algorithm.

Project

I want you to write an insertion sort function. Choose your favorite language, or the one for your interview, and implement a function that sorts a list of values. Use the algorithm I present in this class.

In the example Python implementation, the signature looks like this:

```py
def insertion_sort( items : List[ComparableT] ) -> List[ComparableT]:
```

Verify Sort Algorithm

As a bonus project, write the verify sort algorithm. This is an essential bit of code for unit tests. It also explores concepts that will help you during your interviews.

Verify sort takes an unsorted list and a sorted list. It verifies that the sorted list is indeed the sorted version of the unsorted one.

  • 8 Videos
  • 0 hours 23 minutes
  • 60 Happy Students

Courses Outline

Lesson 1: Insertion Sort: Design and Implementation
Free
Introduction
0:33
Algorithm Design
4:46
Algorithm Complexity
3:43
Verify Sort Algorithm
4:49
Insert Sort Code
3:31
Stable Sort
2:34
Verify Sort Code
2:54
Conclusion
0:17
  • 8 Videos
  • 0 hours 23 minutes
  • 60 Happy Students