Data structures and algorithms in Python

Data Structures and Algorithms in Python by Grow with Google on Udacity.

Efficiency

Efficiency (computational complexity) is how well you are using the computer's resources to get the job done.

List-based collections

Lists

Lists are collections where the elements have an order.

Arrays

Unlike lists, an array has a location called an index—a number associated with that place in the array. Each element stores a value and an index.

Python lists

Behind the scenes a Python list is built as an array but there's a lot of code built in to the Python language running to make that operation possible. Since Python is a "higher level" programming language, there's a lot of code built into the infrastructure that causes your code to actually run much more slowly than you'd think.

Linked lists

Linked lists have an order, but there are no indices. Each element stores a value and a pointer to the next element, so adding and removing elements is more efficient than in an array.

Stacks

Stacks are list based data structures where elements are added and removed from the beginning of the list or the top of the stack. Stacks are "last in first out."

Queues

Queues are list based data structures where elements are added to the end of a list and removed from the beginning of the list. Queues are "first in first out."

Searching and Sorting

Binary search

Compare the target value to the middle element of the list. If they are not equal, the half in which the target cannot lie is eliminated and the process is repeated on the remaining half.

Efficiency of binary search is $O(\log(n))$ .

Bubble sort

Repeatedly iterate through a list comparing adjacent elements and swapping them if they are in the wrong order.

Efficiency of bubble sort is $O(n^2)$ . Space complexity is $O(1)$ . Naive approach.

Merge sort

Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.

Efficiency of merge sort is $O(n\log(n))$ . Auxiliary space is $O(n)$ .

Quick sort

Select a "pivot" element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Efficiency of quick sort is $O(n\log(n))$ . Space complexity is $O(n)$ .