# Big O Exercise: How to create an efficient algorithm to sort a list in python ?

Published: May 28, 2021

Tags: Big 0; Python; List;

Big O exercise

### Exercise

Let's consider the following sorted list with negative and postive values

````l = [-4, -1, 0, 2, 5, 10]`
```

Goal: create an efficient algorithm to square the elements and sort the list:

````[0, 1, 4, 16, 25, 100]`
```

### Solution

My solution, maybe not the optimal solution but the best I found so far:

````l = [-4, -1, 0, 2, 5, 10]`

`min_value = 9999`

`l_new = []`
`for idx,i in enumerate(l):`
`    new_i = i**2`
`    if new_i < min_value: `
`        min_value = new_i`
`        min_value_idx = idx`
`    l_new.append(new_i)`
`    #print(new_i,min_value,min_value_idx)`

`l_pop = []`
`for idx in range(min_value_idx):    `
`    l_pop.append(l_new.pop(0))`

`for value in l_pop:`
`    jdx = len(l_new) - 1`
`    cond = True`
`    while cond:`
`        jdx -= 1`
`        if value > l_new[jdx]:`
`            l_new.insert(jdx+1, value)`
`            cond = False`

`print('l_new',l_new)`
```

returns

````[0, 1, 4, 16, 25, 100]`
```

### Create a function

````def sort_list(l):`

`    nb_count = 0`

`    min_value = 9999`

`    l_new = []`
`    for idx,i in enumerate(l):`
`        new_i = i**2`
`        if new_i < min_value: `
`            min_value = new_i`
`            min_value_idx = idx`
`        l_new.append(new_i)`
`        nb_count += 1`
`        #print(new_i,min_value,min_value_idx)`

`    l_pop = []`
`    for idx in range(min_value_idx):    `
`        l_pop.append(l_new.pop(0))`
`        nb_count += 1`

`    for value in l_pop:`
`        jdx = len(l_new) - 1`
`        cond = True`
`        while cond:`
`            jdx -= 1`
`            if value > l_new[jdx]:`
`                l_new.insert(jdx+1, value)`
`                cond = False`
`                nb_count += 1`
`            if jdx<0: cond = False`

`    return l_new, nb_count`

`l = [-4, -1, 0, 2, 5, 10]`

`l_new, nb_count = sort_list(l)`

`print(l_new)`
`print(nb_count)`
```

returns

````[0, 1, 4, 16, 25, 100]`
`10`
```

### Comparison with python "built-in" functions

````l = [-4, -1, 0, 2, 5, 10]`

`l = [i**2 for i in l]`
`l.sort()`

`print(l)`
```

returns

````[0, 1, 4, 16, 25, 100]`
```

### Create a visualization

````import matplotlib.pyplot as plt`
`import random`
`import math`

`n_list = []`
`nlogn_list = []`
`count_list = []`
`for n in range(10,1000):`

`    l = [random.randint(-100,100) for i in range(n)]`
`    l.sort()`

`    #print(l)`

`    l_new, nb_count = sort_list(l)`

`    n_list.append(n)`
`    nlogn_list.append(n*math.log(n))`
`    count_list.append(nb_count)`

`plt.xlabel('N List Size')`
`plt.ylabel('Iterations')`

`plt.scatter(n_list,count_list)`
`plt.scatter(n_list,nlogn_list)`
```

Image

of