What will we cover in this tutorial

Selection sort is one of the simplest sorting algorithms, which is a good algorithm to start with. While the algorithm is considered to be slow, it has the advantage of not using auxiliary space.

Step 1: Understand the Selection Sort algorithm

The goal of sorting is to take an unsorted array of integers and sort it.

Example given below.

```[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]

to

[3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]

```

The algorithm is the most intuitive way of sorting a list.

It works as follows.

1. Go through the list to be sorted and find the smallest element.
2. Switch the smallest element with the first position.

If you started with the following list.

```[97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]
```

You would now have this list.

```[3, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 7, 48]
```

Notice, that now we have the smallest element in the front of the list, we know that the second smallest element must be somewhere in the list starting from the second position all the way to the end.

Hence, you can repeat step the above 2 steps on the list excluding the first element.

This will give you the following list.

```[3, 7, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 97, 83, 34, 29, 48]
```

Now we have that the first two elements are sorted, while the rest of the list is not sorted.

Hence, we can repeat the two steps again on the unsorted part of the list.

If we continue this until the we reach the end of the list. This should give us a sorted list.

Step 2: Implementation of Selection Sort

A beautiful thing about Selection Sort is that it does not use any auxiliary memory. If you are new to sorting, then this can be a big advantage if sorting large data sets.

The disadvantage of Selection Sort is the time complexity.

We will come back to that later.

The code of Selection Sort can be done in the following manner.

```def selection_sort(list_to_sort):
for i in range(len(list_to_sort)):
index_of_min_value = i
for j in range(i + 1, len(list_to_sort)):
if list_to_sort[j] < list_to_sort[index_of_min_value]:
index_of_min_value = j

list_to_sort[i], list_to_sort[index_of_min_value] = list_to_sort[index_of_min_value], list_to_sort[i]

list_to_sort = [97, 29, 53, 92, 42, 36, 12, 57, 90, 76, 85, 81, 12, 61, 45, 3, 83, 34, 7, 48]
selection_sort(list_to_sort)
print(list_to_sort)
```

This will produce the correct output.

```[3, 7, 12, 12, 29, 34, 36, 42, 45, 48, 53, 57, 61, 76, 81, 83, 85, 90, 92, 97]
```

Step 3: The time complexity of Selection Sort algorithm

Now this is the sad part of this simple algorithm. It does not perform good. A sorting algorithm is considered efficient if it runs in O(n log(n)), which Selection Sort does not.

The simple time complexity analysis is as follows.

Assume we have a list of n unsorted integers. Then the first iteration of the list will make n – 1 comparisons, the second iteration will make n – 2 comparisons, and so forth all the way down to 1 comparison.

This is the sum of 1 to n – 1, which is found by this formula (n – 1)(n – 2)/2, which is O(n^2).

Other than that the algorithm does n swapping of numbers. This is O(n).

This combines the algorithm to O(n + n^2) = O(n^2).

Next Step

This should wake your appetite to understand how you can make more efficient sorting.

Another good example of a simple sorting algorithm is the Insertion Sort algorithm.

For more efficient algorithm you should check out the Merge Sort algorithm.

If you want to be serious about sorting, check out my online course on the subject.

What will we cover in this tutorial?

We will create a heap, or more specifically, a max-heap. A max-heap is a tree structure where the node value of every parent is greater or equal to the children.

In this tutorial we will implement a max-heap with a binary tree and use a randomized approach to keep it balanced.

You might be wondering why to make it randomized. Simply, said, to keep it simple and keep operations on average O(log(n)).

Step 1: Recall what a max-heap is

A max-heap is a tree structure where the node value of every parent is greater or equal to the children.

A heap will have two primary functions.

1. Insert an element and still keep the max-heap structure.
2. Get and remove maximum element (the element at the root) and still keep the max-heap structure.

The goal is to be able to do these operations in O(log(n)) time.

Step 2: Understand what a randomized algorithm can do for you

Randomized algorithms help you achieve great performance on average while keeping the algorithms simple.

To get keep the operations of a heap at worst-case O(log(n)), you need to keep the binary tree structure balanced. This requires complex ways to ensure that.

Instead, just put in the leaves in the three randomly, and you will get the same result with very high probability. Hence, you will end up with an average time of O(log(n)) for the operations.

Step 3: Insert into a max-heap

Now to the fun part. The code.

Let’s start simple and create a Node to represent the nodes in the binary tree, which will represent the max-heap.

```class Node:
def __init__(self, element):
self.element = element
self.left = None
self.right = None
```

The node needs to be able to keep the element (which should be comparable), and a left and right child.

From the above Node class you can create an arbitrary binary tree.

The max-heap insert function can be implemented by a recursive and randomized approach in the following manner.

```import random

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger then node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

# Choose a random node (here is the randomness hidden)
if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
if self.head is None:
else:
```

The function insert(…) checks for the special case, if there are no nodes in the binary tree so far and inserts if so. Otherwise, it will forward the call to the recursive and randomized function _insert(….), which also takes the head (root) of the tree as argument.

A recursive function in this case could be at any node, but starting from the head (root) node. It will do the same all the way down.

1. Check if element of node is smaller than element to insert. If so, switch them.
2. Check if node has a free child (left or right). If so, use it to insert new node with element and return.
3. If none of the above, choose a random child (left or right) and call recursive down.

That is it. It will most likely create a well balanced binary tree.

See example here.

```               +---------------36---------------+
+-------29-------+              +-------34-------+
+---27---+      +---20---+      +---32---+      +---33---+
+- 3-+  +-13-+  +- 6-+  +- 2-+  +-24-+  +-31-+  +-25-+  +-25-+
0   1           4              16               6
```

In simple ascii representation of the binary tree representing the max-heap. That the binary tree keeps a balance like that ensures that the insertion will be O(log(n)) on average.

Step 4: Delete the maximum element from the heap (and return it)

Deleting the maximum element will remove the root (head) of the binary tree. Then we need to take the larger child and move it up. That obviously makes an empty space in the child below. Hence, we need to do the same operation below.

This sounds recursive, doesn’t it?

```import random

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger than node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
if self.head is None:
else:

def get_max(self):

def _delete_max(self, node):
if node.left is None and node.right is None:
return None

if node.left is None:
return node.right

if node.right is None:
return node.left

if node.right.element > node.left.element:
node.element = node.right.element
node.right = self._delete_max(node.right)
return node
else:
node.element = node.left.element
node.left = self._delete_max(node.left)
return node

def delete_max(self):
if self.head is None:
return None

return max_element
```

The delete_max function takes care of the special case where there are no elements (or nodes) in the binary tree. Then it takes the largest element and calls the recursive _delete_max(…) function with the head (root) as argument.

The _delete_max(…) function does the following.

1. Checks for special case where node has no children. If so, return None.
2. Check if one child is not there, if so return the existing child.
3. Otherwise, take the child with the larger element. Take the larger element and assign it to node (remember, we have removed the element form the calling node), and call recursive down with larger child on _delete_max(…) and assign result to larger child node.

That can be a bit confusing at first. But try it out.

This operation also only has O(log(n)) performance on average. And as elements are put randomly, then removing them in order (maximum elements), will remove elements randomly and keep the binary tree balanced on average case.

Step 5: The full code and a simple print function of the tree

The full code can be found here.

```import random

class Node:
def __init__(self, element):
self.element = element
self.left = None
self.right = None

class Heap:
def __init__(self):

def _insert(self, element, node):
# if element is larger than node.element, switch
if element > node.element:
element, node.element = node.element, element

# check if available node
if node.left is None:
node.left = Node(element)
return
if node.right is None:
node.right = Node(element)
return

if random.randint(0, 1) == 0:
self._insert(element, node.left)
else:
self._insert(element, node.right)

def insert(self, element):
if self.head is None:
else:

def get_max(self):

def _delete_max(self, node):
if node.left is None and node.right is None:
return None

if node.left is None:
return node.right

if node.right is None:
return node.left

if node.right.element > node.left.element:
node.element = node.right.element
node.right = self._delete_max(node.right)
return node
else:
node.element = node.left.element
node.left = self._delete_max(node.left)
return node

def delete_max(self):
if self.head is None:
return None

return max_element

def _get_depth(self, node):
if node is None:
return 0
left = self._get_depth(node.left)
right = self._get_depth(node.right)
if left > right:
return 1 + left
else:
return 1 + right

def get_depth(self):

def _print_heap(self, current_level, request_level, depth, node):
characters_per_level = 4*2**depth
characters_per_node = characters_per_level // (2**(current_level + 1))
if current_level == request_level:
if node is not None:
space_fill = characters_per_node // 4 - 1
if request_level == depth - 1:
print(' '*space_fill + ' ' + ' '*space_fill + f'{node.element:2d}' + ' '*space_fill + ' ' + ' '*space_fill, end='')
else:
print(' '*space_fill + '+' + '-'*space_fill + f'{node.element:2d}' + '-'*space_fill + '+' + ' '*space_fill, end='')
else:
print(' '*characters_per_node, end='')
else:
if node is not None:
self._print_heap(current_level + 1, request_level, depth, node.left)
self._print_heap(current_level + 1, request_level, depth, node.right)
else:
self._print_heap(current_level + 1, request_level, depth, None)
self._print_heap(current_level + 1, request_level, depth, None)

def print_heap(self):
for i in range(depth):
self._print_heap(0, i, depth, self.head)
print()
```

Notice that the print function also is recursive.

Understand binary serach

The whole idea behind binary search is that you can take advantage of having the list you search in ordered.

Say, we need to search for 7 and we look at the element in the middle of the list.

Then we can conclude, in this example, that 7 is not part of the right side of the list, as all numbers must be greater than 10. That is because the list is ordered.

Next we ask the in the middle of the left side of the list which is left unknown is 7 is there.

As -9 is less than 7, we know that 7 cannot be before in the list and are left with the remaining element between -9 and 10.

As -3 is less than 7, we know that if 7 is part of the list, then it must be to the right of -3. Also, we know it must be before 10 (our first comparison).

Hence, it can only be in the last spot left. But as it is 8, we now know that 7 is not part of the list.

Why is that impressive?

Consider if the list was unsorted. Then you would have to look through the entire list to make sure 7 was not part of it.

In terms of complexity that means if the list contains N element, it must make N comparisons to search of an element. That is O(N) time complexity.

The binary search on the other hand is way more efficient. For each comparison the algorithm can skip one half of the list. That is O(log(N)) time complexity.

The source code

```def recursive_binary_search(my_list, element):
return recursive_binary_search_internal(my_list, element, 0, len(my_list) - 1)

def recursive_binary_search_internal(my_list, element, low, high):
if low > high:
return False
else:
mid = (low + high)//2
if my_list[mid] == element:
return True
else:
if my_list[mid] > element:
return recursive_binary_search_internal(my_list, element, low, mid - 1)
else:
return recursive_binary_search_internal(my_list, element, mid + 1, high)

def binary_search(my_list, element):
low = 0
high = len(my_list) - 1
while low <= high:
mid = (low + high)//2
if my_list[mid] == element:
return True
else:
if my_list[mid] > element:
high = mid - 1
else:
low = mid + 1
return False

def main():
my_list = [-29, -16, -15, -9, -6, -3, 8, 10, 17, 19, 27, 47, 54, 56, 60]
print(my_list)
element = 56
print("Binary Search:", binary_search(my_list, element), element)
print("Recursive Binary Search:", recursive_binary_search(my_list, element), element)

if __name__ == "__main__":
main()
```

There are two implementations of the binary search in the above example.

Want to learn how to sort a list?

Understand Merge Sort in 6 Minutes

Merge sort is one of the algorithms you need to master. Why?

Because it is in the class of efficient algorithms and is easy to understand.

But what does efficient mean?

Let’s get back to that. First how does Merge Sort work?

It takes the list and breaks it down into two sub lists. Then it takes these sublists and break them down into two. This process continues until there is only 1 element in each sublist.

And a list containing only 1 element, is a sorted list.

It then takes two sublists and merge them together. Notice, that each of these sublists (in the first place, the sublists only contain 1 element each) are sorted.

Then it is effective to merge them together sorted. The algorithm looks at the first element of each sorted sublist and takes the smaller element first.

This process continues all the way down.

Then the next row is taken of sublists. Again, the sample algorithm is used to merge them together. Take the smaller element of the two and add them to the new list. This continues.

This process continues until we end up with one list.

Which by magic (or the logic behind the algorithm) is sorted.

Time complexity

Well, we talked about it is one of the efficient sorting algorithm. That means it runs in O(N log(N)) time.

That means, if you have a list of N unsorted elements, it will take N log(N) operations.

Is that true for Merge Sort?

How many layers do you have in the algorithm?

Well, for each layer you half the size of each sublist. You can do that log(N) times.

For each layer, you do N comparisons. That results in N log(N) operations, hence, the O(N log(N)) time complexity.

The implementation of Merge Sort in Python

```def merge_sort(my_list):
if len(my_list) <= 1:
return my_list

mid = len(my_list)//2
left_list = my_list[:mid]
right_list = my_list[mid:]

merge_sort(left_list)
merge_sort(right_list)

index_left = 0
index_right = 0
index_main = 0

while index_left < len(left_list) and index_right < len(right_list):
if right_list[index_right] < left_list[index_left]:
my_list[index_main] = right_list[index_right]
index_right += 1
index_main += 1
else:
my_list[index_main] = left_list[index_left]
index_left += 1
index_main += 1

while index_left < len(left_list):
my_list[index_main] = left_list[index_left]
index_left += 1
index_main += 1

while index_right < len(right_list):
my_list[index_main] = right_list[index_right]
index_right += 1
index_main += 1

def main():
my_list = [19, 56, 8, -6, -3, 27, -9, -29]
print(my_list)
merge_sort(my_list)
print(my_list)

if __name__ == "__main__":
main()
```

That is awesome.

Want to learn more about sorting. Check out the Insertion Sort, which is also one of the sorting algorithms you need to master. It is not as efficient, but it has one advantage you need to understand.

Understand the algorithm

Insertion sort is an awesome algorithm that has some quite interesting use-cases due to it nature.

First understand the basics of it.

Consider the list of integers.

The above list has 10 elements. Now if you only consider the list of the first element (number 3), then that part is actually sorted. If number 3 was the only number in the list, then it would be sorted.

Now consider the list of the first two elements.

Then we have the list of two elements, 3 and 5. Here we are lucky, as this is still sorted.

Now for the next element, 1, we are a bit out of luck, because if we just added that element to part of the list (the green part), then it would not be sorted.

If one was added, we would need to swap it down until it is on place. First swapping 1 with 5.

Then swapping 1 with 3. Then we are having a ordered list again, that is a list of the 3 first elements (the green part of the list below).

Hence, the process is to think of the first element as a list and realize it is ordered. Then insert one element at the time. For each element inserted, swap it down until it is on place.

Why is Insertion Sort great to know?

Well, first of all it is simple to understand. Second of all, it is easy to implement (see the code below). But that is not the exiting stuff.

Well, what is it?

It has some interesting use case. See.

• If you were to keep an ordered list in memory as part of your program.
• But it also had a twist.
• Someone would keep coming with new numbers all the time, and still ask you to keep the list ordered.
• Then the efficiency of keeping this list ordered is good.

Why?

Because if the list is ordered and you need to add another element, you just follow the above procedure.

The worst case run-time for a list of N element is O(N).

What is the catch?

Well, the performance of the algorithm is not good. That is, there are more efficient algorithms out there to sort N elements.

Let’s analyze.

For the first element you use 1 operation. The second element 2 operations. The third element 3 operations. Wait a minute, isn’t that this formula?

1 + 2 + 3 + 4 + … + N = N(N+1)/2

Which unfortunately gives a performance of O(N^2).

Well, because of the use-case explained above. That you can keep it ordered and with low cost insert an element into it.

The code

```import random

def generate_random_list(n):
# n is the length of the list
my_list = []
for i in range(n):
my_list.append(random.randint(0, 4*n))
return my_list

def insertion_sort(my_list):
for i in range(1, len(my_list)):
for j in range(i, 0, -1):
if my_list[j] < my_list[j-1]:
my_list[j], my_list[j-1] = my_list[j-1], my_list[j]
else:
break

def main():
my_list = generate_random_list(20)
print(my_list)
insertion_sort(my_list)
print(my_list)

if __name__ == "__main__":
main()
```

The above code implements the algorithm (see only 7 lines of code) and tests it.

I hope you enjoyed.

What will we cover?

• What is Bubble sort and how does it work?
• How to implement it in Python
• How to evaluate the time complexity of the Bubble sort algorithm

What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

```def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]
```

An simple illustration of how you can use it.

```import random

def generate_random_list(n):
my_list = []
for i in range(n):
my_list.append(random.randint(0, n))
return my_list

def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

my_list = generate_random_list(20)
print(my_list)
bubble_sort(my_list)
print(my_list)

```

Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

• Outer for-loop: N times
• Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

• N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

```import random
import cProfile

def generate_random_list(n):
return [random.randint(0, 4*n) for i in range(n)]

def bubble_sort(my_list):
for i in range(len(my_list), 1, -1):
for j in range(1, i):
if my_list[j-1] > my_list[j]:
my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

def profile_bubble_sort(n):
my_list = generate_random_list(n)
bubble_sort(my_list)

cProfile.run("profile_bubble_sort(10000)")
```

It will result in an output in the following manner.

```         56372 function calls in 11.056 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000   11.056   11.056 <string>:1(<module>)
1    0.000    0.000   11.055   11.055 BubbleSortProfiling.py:16(profile_bubble_sort)
1    0.000    0.000    0.034    0.034 BubbleSortProfiling.py:5(generate_random_list)
1    0.008    0.008    0.034    0.034 BubbleSortProfiling.py:6(<listcomp>)
1   11.021   11.021   11.021   11.021 BubbleSortProfiling.py:9(bubble_sort)
10000    0.010    0.000    0.022    0.000 random.py:200(randrange)
10000    0.005    0.000    0.027    0.000 random.py:244(randint)
10000    0.007    0.000    0.012    0.000 random.py:250(_randbelow_with_getrandbits)
1    0.000    0.000   11.056   11.056 {built-in method builtins.exec}
1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
10000    0.001    0.000    0.001    0.000 {method 'bit_length' of 'int' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
16364    0.003    0.000    0.003    0.000 {method 'getrandbits' of '_random.Random' objects}
```

You get the time spend in Bubble sort by looking the highlighted line. In the column cumtime you get the time spend in total in the function.

By collecting the run-time for various sizes of lists, we get the following graph.

The graph has a O(n^2) growth as expected.