---
jupytext:
  formats: content_md///md:myst,content///ipynb
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.13.8
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

(projects:python:simple-list)=
# Simple List Algorithms

In this project we implement simple algorithms related to lists like sorting a list or finding special values. The purpose of the projecct is threefold:
* familiarize yourself with Python's syntax,
* learn to algorithmize, that is, how to combine available building blocks to solve a task,
* see and understand how basic algorithms frequently used in data science work.

Before you work through the project you should have read [](python:crash:blocks). Restrict yourself to Python features discussed there. Don't use ready-made library functions.

```{important}
Don't use `list` as name for a variable holding some list, although this would be quite expressive. Several names like `print` and `int` and `list` are already occupied by Python. Python won't complain about reusing some of it's predefined names as variables, but it's considered bad practice.
```

## Maxmium of a List

Given a list of integers we want to find the list's greatest value.

**Task:** Describe a process (that is, algorithm) to find the maximum value of a list in your words, not Python code. Remember that the list may be of arbitrary length. For simplicity you may assume that the list is not empty.

**Solution:**

```{code-cell} ipython3
# your solution
```

**Task:** Implement your algorithm in Python. Proceed as follows:
1. Create a function `get_max` which takes a list as argument and, for the moment, always returns the length of the list.
2. Create a sample list, pass it to your function, and print the returned value to the screen.
3. If the framework is working correctly, implement your algorithm in `get_max` and make the function return the maximum value.
4. Test your code with several different sample lists. Include pathological cases like `[1, 1, 1]` and `[1]`.

**Solution:**

```{code-cell} ipython3
# your solution
```

**Task:** What happens if you test your code with an empty list? Now add some code to your function to check whether the list is empty. If the list is empty `get_max` should print a message and return 0.

**Solution:**

```{code-cell} ipython3
# your solution
```

## Mean of a List

Given a list of floats we want to find the list's mean.

**Task:** Describe an algorithm for calculating the mean of a list. Assume that the list has at least one item.

**Solution:**

```{code-cell} ipython3
# your solution
```

**Task:** Implement your algorithm in Python. Proceed as follows:
1. Create a function `get_mean` which takes a list as argument and, for the moment, always returns the length of the list.
2. Create a sample list, pass it to your function, and print the returned value to the screen.
3. If the framework is working correctly, implement your algorithm in `get_mean` and make the function return the list's mean.
4. Test your code with several different sample lists. Include obvious cases like `[-1, -1, 1, 1]` and pathological cases like `[1]`.

**Solution:**

```{code-cell} ipython3
# your solution
```

**Task:** What happens if you test your code with an empty list? Now add some code to your function to check whether the list is empty. If the list is empty `get_mean` should print a message and return 0.

**Solution:**

```{code-cell} ipython3
# your solution
```

## Count Values

Given a list of integers we want to count how often a given integer occurs in the list.

**Task:** Write a function `count_value` taking two arguments (the list and an integer) and returning the number of occurrences of the integer in the list. Proceed step by step as before. How to handle empty lists here?

**Solution:**

```{code-cell} ipython3
# your solution
```

## Sorting a List

There exist plenty of [algorithms for sorting](https://en.wikipedia.org/wiki/Sorting_algorithm) values in lists. Here we consider [selection sort](https://en.wikipedia.org/wiki/Selection_sort) for sorting a list of integers.

```{figure} selection-sort.gif
---
alt: animation of selection sort algorithm showing which items are swapped in which order
---
Selection sorts devides the list into two parts: sorted items and unsorted items. It repeatedly walks (blue) through the unsorted items to find the smallest (red) unsorted item. Then it swaps the first unsorted item with the smallest unsorted item. The swapped item then belongs to the sorted part (yellow). Source: Joestape89, [wikipedia.org](https://en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif), [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0/deed.en), modified by the author.
```

**Task:** Write a function `sort` taking a list and returning the sorted list. Proceed step by step as before. Don't forget to extensively test your code!

**Solution:**

```{code-cell} ipython3
# your solution
```
