MISSION 174

# Stacks

In the last lesson, we learned about arrays and linked lists. In this lesson, we'll cover a more concrete usage of both data structures by talking about sorting. If you've used a Python list, you're probably familiar with using the list.sort() method to order values.

While using `list.sort` is sufficient in some cases, the default sorting behavior isn't ideal, such as when we have a want to sort a custom data structure, we still want everything sorted when we're working with data that is too large to fit into memory, or we want a custom ordering.

To get around the above use cases, you'll have to find a different sorting mechanism or code your own. In this lesson, we'll focus on how sorting arrays and lists that will complete in the fastest time. To understand how the different sorting works so you can begin sorting arrays and lists, we'll be using a set of bank transaction data that originally came from a Kaggle competition.

While there are more complex sorting algorithms, this lesson on sorting arrays and lists will focus on selection sort, bubble sort, and insertion sort. In addition, we'll see the profile of each sorting algorithm including the time and space complexity of it.

In addition to sorting arrays and lists and learning the trade-offs involved with each sorting algorithm, you’ll get to apply what you’ve learned from within your browser; there's no need to use your own machine to do the exercises. The Python environment inside of this course includes answer-checking to ensure you've fully mastered each concept before learning the next.

#### Objectives

• Learn the different types of sorting algorithms.
• Learn how to implement each sorting algorithm.
• Learn how to profile each sorting algorithm.

#### Lesson Outline

1. Sorting Arrays
2. Sorting Arrays
3. Swapping Elements
4. Selection Sort
5. Profiling The Selection Sort
6. Bubble Sort
7. Profiling The Bubble Sort
8. Insertion Sort
9. Insertion Sort
10. Profiling The Insertion Sort
11. Comparing Sorting Algorithms
12. Takeaways