Questions #1

def fact (N, acc = 1 ):
if N == 1 :
return acc
else :
return fact(N - 1 , acc * N)

Describe quicksort. What is its complexity?
At the first stage, a reference element is selected. Most often it is taken from the middle of the array. Then the first element of the array is sequentially compared with the last one, the second with the penultimate one, and so on. If the element to the left of the anchor element is larger than the right element, they are swapped. When they reach the anchor element, the iteration is considered completed.
Further, the algorithm described above is applied to two subarrays. The first one is from the first element to the reference element (not inclusive), the second one is from the reference element to the last one.
Recursive descent continues until the lengths of the subarrays are equal to one.
The average complexity of quicksort is N * log(N).
What is O-notation?
todo

Tasks for algorithms

• 
  How to extract elements of an array in random order without repetition?
  

Practice

• 
  Write a decorator that displays the running time of an arbitrary function.
  
• 
  Write a decorator that returns either a result or an instance of an exception.
  
• 
  Write a Fibonacci generator from a and b.
  
• 
  Get unicode text from a file.
  
• 
  Write a Fibonacci number generator like def fib(a=1, b=2):
  

A task on ORM

class City(models.Model):
name = models.CharField()
classPerson(models.Model):
name = models.CharField()
city = models.ForeignKey(City)

• 
  Display a list of people and cities where they live?
  
• 
  Output all people living in city N
  
• 
  Display the 5 cities with the largest population, sorted in descending order.