Study Web

Weekly Programming Topics

Sorting, Complexity and Recursion

Sorting, Complexity & · Recursion

Sorting, Complexity and Recursion

Sorting, Complexity & Recursion

Today we will cover the following topics:

  • Sorting
  • Complexity (Big O Notation)
  • Recursion
Problem Scenario
Online Store 1-3
  • You are a programmer working for a large online store.
  • When customers search for products, the website must sort results by:
  • Price (lowest to highest)
  • Customer rating
  • Popularity
  • Today the store has:
  • 500 products
  • During a big sale it might have:
  • 5,000,000 products If sorting the products takes too long:
  • The page loads slowly
  • Customers leave the website
  • The company loses money
Warmup Activity
Group Debugging
  • Pair up or form a team of 3.
  • Your task is to download the debugging exercise.
  • Modules -> Lectures -> Week 09 -> Download examples
  • Compete to see which team can fix the code and show the correct answer.
  • File is debugging.py 1-4
1-5
Sorting Lists
Theory
  • Unorganized data is difficult to search or analyse.
  • Remember the binary search algorithm from week 7? It can't be used on unorganised datasets.
  • We sort our arrays so the data is more meaningful, it's also the first step towards further processing or searching.
1-6
Insertion Sort
Pseudocode Using the Pseudocode try to implement your own sorting function
1-7
Python Sort
Built into lists The easiest way, just remember Python uses Timsort Complexity: O(n log n) It's not magic it's just an implementation of a sorting algorithm.

Different Sorting Algorithms

1-8

There are many different algorithms we can choose from. Some of them are slower than others Later we will look at which ones are faster than others. We still learn them to understand the concepts and practice things for ourselves.

Complexity
What is an Algorithm
  • An algorithm is formally defined as (Knuth, 1968):
  • Finite (it stops);
  • Definite (precise, not subjective);
  • An Effective procedure (i.e can be carried out); and
  • Produces output (has some result or effect)
  • Takes input. 1-9

Complexity – Theory

1-10

Source: https://www.bigocheatsheet.com/

  • It takes time for our code to execute.
  • Most of the time it isn't a problem.
  • However with large datasets, or when time is critical or hardware is limited we need to be aware.
  • A larger input doesn't always increase linearly with the time taken

Big O Notation

  • Big O is a way of expressing the efficiency of an algorithm, looking at the time or space requirements.
  • We have an expression which tells us the growth rate using input size n
  • Big O describes how runtime grows as input size increases. 1-11
1-12
Complexity
Big O Notation 1-13 Source: https://www.bigocheatsheet.com/
O(n)
Linear
  • Proportional Growth: If the input size doubles, the number of operations and execution time roughly double as well. 1-14

Source: https://levelup.gitconnected.com/big-o-time-complexity-what-it-is- and-why-it-matters-for-your-code-6c08dd97ad59

O(n^2) – Quadratic

  • Performance degrades quickly with larger inputs, often due to nested loops (e.g., Bubble Sort). 1-15

Source: https://levelup.gitconnected.com/big-o-time-complexity-what-it-is- and-why-it-matters-for-your-code-6c08dd97ad59

O(2^n) – Exponential

  • Becomes infeasible very quickly as input size grows (e.g., naive recursive Fibonacci). 1-16

Source:

https://codefellows.github.io/common_curriculum/data_structures_and_algorithms/Code _401/class-05/resources/big_oh.html

O(log n) – Logarithmic

  • Very efficient; problem size is halved with each step (e.g., binary search on a sorted array). 1-17

Source: https://levelup.gitconnected.com/big-o-time-complexity-what-it-is- and-why-it-matters-for-your-code-6c08dd97ad59

O(1) – Constant

  • If an algorithm has an O(1), this means that, no matter what the value of n is, the amount of operations needed to solve the problem stays constant. 1-18

Source: https://levelup.gitconnected.com/big-o-time-complexity-what-it-is- and-why-it-matters-for-your-code-6c08dd97ad59

Big O – Others

  • O(n log n) (Linearithmic Time): Slower than linear but faster than quadratic (e.g., efficient sorting algorithms like Merge Sort).
  • O(n!) (Factorial Time): The worst, involving considering all permutations (e.g., brute-force solution to the Traveling Salesman problem) 1-19

Different Sorting Algorithms + Complexity

1-20

Big O Example

1-21

Download the example code and look at the complexity.py file. It has some example code with a large input of random numbers and then times them. This will demonstrate different complexities.

1-22

Implement the count_halvings function and compare it to the other times. BONUS: At the end of the class try out the fibonacci function, compare it, then try an iterative approach and compare it again.

Recursion – Theory

1-23
Source: https://www.youtube.com/watch?v=ngCos392W4w
  • At it's simplest, recursion is a technique where a function will call itself to solve a problem
  • Recursion solves a big problem by solving smaller versions of the same problem.
  • What do you imagine can happen if we're not careful?
  • Infinite loops! 1-24
  • We use a base case, a condition to stop the recursion.
  • We perform our calculation
  • We recursively call our function with a reduced or simpler input. 1-25

Recursion – Python

  • Use the pseudocode and implement your own version 1-26

Recursion – Stack

1-27

Source: https://medium.com/analytics-vidhya/recursion-vs-explicit-stacks- 44d9bd14cb0a Be careful using recursion in Python eventually we will see the following: RecursionError: maximum recursion depth exceeded

1-28

Source: https://medium.com/analytics-vidhya/recursion-vs-explicit-stacks- 44d9bd14cb0a

  • Think of a (any) stack like a pile of plates. We can add plates on top, but we can only take off the top of the pile.

Recursion – Binary Search

1-29

Implement a recursive binary search. Compare the solution to your own from week 7. What do you think about recursion? What are the advantages or disadvantages? Share your opinions with the class.

Recursion – Fibonacci

1-30

Implement the Fibonacci algorithm in the complexity.py File. Try to implement a version without recursion, use iteration. How does it compare?

Recap

  • What did we learn?
  • What do you think is most important to keep in mind?
  • What concepts today will you apply to your custom project? 1-31
Recursion
9.4 HD M Maze Search 1-32 You must use recursion for this task, if you do not you will not pass. You must also explain your solution in detail and answer any questions, or you will not complete it.

Music Player

1-33
  • Complete each to the highest level you want. You will demonstrate your highest level. Complete and submit the pass before upgrading and submitting the credit and so forth.