An

**algorithm**is a

*step-by-step procedure*, that is,

**a finite sequence of well-defined instructions for solving problems or accomplishing tasks**.

# Quick sort

**Quick sort is a very efficient sorting algorithm**.* Our list is partitioned into two lists. The first one will hold all the list's values smaller than the specified value, say pivot* (it is going to be the first element of the list, myList[0], in our implementation) *and the second list will hold all the values greater than the pivot*.

Quicksort partitions the list and then calls itself recursively twice to sort the two resulting or remaining sub-lists.

import random import time def timing(func): # We are going to use decorators to compare different algorithms. def wrapper(*arg, **kw): # args and kw collect all arguments and keywords. '''source: http://www.daniweb.com/code/snippet368.html''' t1 = time.time() res = func(*arg, **kw) # The wrapped function is executed at this time. t2 = time.time() # Finally, we print the function's name and the time taken by the function to execute (t1 - t2) print("%r %2.2f ms" % \ (func.__name__, (t2 - t1) * 1000)) return wrapper # This extra function is going to generate a random list of integers. def generateRandom(minimum = 1, maximum = 100, numberElements = 10): return [int(random.randint(minimum, maximum)) for e in range(numberElements) ] @timing def comparing_default_sort(): # We are going to compare quick_sort with Python List sort() method. myRandomList = generateRandom(1, 100, 20) myRandomList.sort() print(myRandomList) def quick_sort(myList): if len(myList) <= 1: return myList else: return quick_sort([x for x in myList[1:] if x < myList[0]]) \ + [myList[0]] + quick_sort([x for x in myList[1:] if x >= myList[0]]) if __name__ == '__main__': comparing_quick_sort() comparing_default_sort()[19, 30, 40, 44, 46, 51, 52, 54, 55, 58, 61, 62, 65, 66, 67, 71, 80, 82, 84, 93] 'comparing_quick_sort' 0.07 ms

[5, 8, 10, 23, 25, 30, 32, 38, 43, 53, 53, 53, 54, 58, 61, 64, 69, 75, 100, 100] 'comparing_default_sort' 0.05 ms

# Bubble sort

**Bubble sort** is one of the simplest sorting algorithms, but performs poorly in real world use. This sorting algorithm works by repeatedly **comparing and swapping each pair of adjacent elements if they are not in order**.

def bubble_sort(myList): n = len(myList) for i in range(n): # Notice that after each iteration, one less element (the last one) is needed to be compared (it is already in the right place) until there are no more elements left to be compared. for j in range(0, n-i-1): if myList[j] > myList[j+1] : myList[j], myList[j+1] = myList[j+1], myList[j] return myList

# Selection sort

**Selection sort** is an in-place comparison-based sorting algorithm. In this algorithm, the list is divided into two sublists: *a sorted sublist of items that is built up from left to right and a second sublist of the remaining unsorted items*.

Initially, the sorted part of the list is empty and the unsorted part is the given list. The whole list is scanned sequentially and the smallest value in the list is placed in the first position of the sorted sublist. After that, the second smallest element is selected and placed in the second position by scanning among the unsorted elements of the list. The process obviously continues until the whole list is sorted.

def selection_sort(myList): n = len(myList) for i in range(n): # Find the minimum element in the remaining unsorted list min_index = i for j in range(i+1, n): if myList[min_index] > myList[j]: min_index = j # Swap the found minimum element with the first element myList[i], myList[min_index] = myList[min_index], myList[i] return myList if __name__ == '__main__': comparing(bubble_sort) comparing(selection_sort) comparing(quick_sort) comparing_default_sort()[12, 15, 24, 29, 47, 49, 50, 50, 57, 64, 67, 67, 68, 73, 75, 80, 88, 94, 95, 99] 'comparing' 0.08 ms

[1, 10, 20, 27, 33, 36, 36, 36, 59, 60, 65, 68, 70, 72, 76, 81, 83, 86, 99, 100] 'comparing' 0.06 ms

[3, 5, 8, 28, 29, 35, 52, 57, 69, 72, 73, 74, 79, 82, 84, 85, 87, 90, 98, 99] 'comparing' 0.06 ms

[5, 7, 8, 14, 14, 34, 47, 55, 59, 60, 68, 74, 74, 76, 78, 79, 82, 89, 97, 98] 'comparing_default_sort' 0.03 ms

# Visualizing Sorting Algorithms

We are going to use **Matplotlib**. It is *a multi-platform data visualization library* built on NumPy arrays for the Python programming language.

import matplotlib.pyplot as plt import numpy as np def bubble_sort(myList): n = len(myList) x = np.arange(0, n, 1) for i in range(n): # Notice that after each iteration, one less element (the last one) is needed to be compared (it is already in the right place) until there are no more elements left to be compared. for j in range(0, n-i-1): plt.bar(x, myList) # It makes a bar plot or bar chart. It takes a list of positions (x) and values (our list). plt.pause(0.01) # It is used to pause for interval seconds. plt.clf() # It clears the current figure. if myList[j] > myList[j+1] : myList[j], myList[j+1] = myList[j+1], myList[j] plt.show() # It displays all open figures. return myList

# Merge Sort

Merge Sort is a divide and conquer sorting algorithm.

def merge_sort(list): if len(list) > 1: # The case base is that the list contains one or zero elements. left_list, right_list = list[:len(list)//2], list[len(list)//2:] len_left_list, len_right_list = len(left_list), len(right_list) merge_sort(left_list) merge_sort(right_list)

It divides and conquers by finding the mid-value and recursively calling itself to sort the left and right sub-lists. After that, we combine by merging the two sorted sub-lists into a single one.

left_index, right_index, merge_index = 0, 0, 0 while left_index < len_left_list and right_index < len_right_list: # We repeat the first loop while there are still untaken elements in the left or the right sub-lists. if left_list[left_index] < right_list[right_index]: # We repeatedly compare the lowest "unseen" or "untaken" element in the left sub-list with the lowest untaken element in the right sub-list and copy the lower of the two in our merged list. list[merge_index] = left_list[left_index] left_index += 1 else: list[merge_index] = right_list[right_index] right_index += 1 merge_index += 1 while left_index < len_left_list: # The second loop is to copy the remaining or unseen elements from the left sub-list. list[merge_index] = left_list[left_index] left_index += 1 merge_index += 1 while right_index < len_right_list: # The third loop is to copy the remaining or unseen elements from the right sub-list. list[merge_index] = right_list[right_index] right_index += 1 merge_index += 1 def main(): myRandomList = generateRandom(1, 100, 30) print(myRandomList) merge_sort(myRandomList) print(myRandomList)

# Binary Search

Binary Search is an algorithm for finding an "item" from a sorted list of elements. It is kind of a guessing game.

def generateRandom(minimum=1, maximum=100, numberElements=10): return list(set([int(random.randint(minimum, maximum)) for e in range(numberElements)])) def binary_search(list, item, begin, end): # Begin is the current minimum reasonable guess for this round. End is the current maximum reasonable guess for this round. while begin <= end: # The end of the circle is when "begin" is greater than "end". The item is not on our list. midpoint = begin + (end - begin) // 2 # We are going to guess or check if item is in the middle. if list[midpoint] == item: # We've guessed the number! return midpoint elif item < list[midpoint]: # The guess is too high, we set the "end" to be one smaller than the guess. end = midpoint - 1 else: begin = midpoint + 1 The guess is too low, we set the "begin" to be one smaller than the guess. return None

def binary_search(list, item, begin, end): # Recursive implementation if begin <= end: midpoint = begin + (end - begin) // 2 if list[midpoint] == item: return midpoint elif item < list[midpoint]: return binary_search(list, item, begin, midpoint-1) else: return binary_search(list, item, midpoint+1, end) return None def main(): myRandomList = generateRandom(1, 100, 30) myRandomList.sort() item_a = random.choice(myRandomList) print(myRandomList) print(item_a) print(binary_search(myRandomList, item_a, 0, len(myRandomList)-1)) if __name__ == '__main__': main()

# Random Walk

Consider a sailor who gets out of a corner pub completely drunk, in a city where all blocks are in perfect squares. The drunken sailor walks from one corner of a block to the next, but then in this corner forgets where he was coming from, where he is going, and even who he is. He keeps going, picking the next direction where to go randomly among the four possible ways, forming a random walking pattern.

We use Monte Carlo methods to simulate his walk and answer questions like how far he, on average, will go after N steps. What is the longest walk he can take so that on average he will end up K blocks or fewer from the pub?

import random import numpy import pylab def random_walk(n): # It simulates the sailor's random walk with n steps. This code is inspired by Socratica (It makes high-quality educational videos on programming). x, y = 0, 0 for i in range(n): (dx, dy) = random.choice([(0, 1), (0, -1), (1, 0), (-1, 0)]) x += dx y += dy return (x, y) def far_fromPub(x, y, distancePub): # Is the sailor (x, y) very far from the pub? return False if abs(x) + abs(y)<= distancePub else True def walk_size(walk_size, distancePub, number_of_walks): # It makes the Monte Carlo simulation. walk_size-1 is the maximum number of sailor's steps, distancePub is the distance considered to be far from the Pub, number_of_walks is the number of simulations that we are going to run. a = [0]*walk_size b = [100]*walk_size average = [0]*walk_size for walk_length in range(1, walk_size): # walk_length is the number of sailor's steps between 1 and (walk-size-1) really_close_pub = 0 # It stores the times that the sailor ended up not very far from the pub distance = 0 # It stores the distance of the sailor's walks. for i in range(number_of_walks): (x, y) = random_walk(walk_length) distance += abs(x)+abs(y) if not far_fromPub(x, y, distancePub): really_close_pub += 1 really_close_percentage = float(really_close_pub)/number_of_walks # It calculates the percentage of times that the sailor did not venture very far from the pub. average_distance = float(distance)/number_of_walks # It calculates the average distance that the sailor walked. a[walk_length] = walk_length b[walk_length] = 100 * really_close_percentage average[walk_length] = average_distance print(f"Walk size = {walk_length:.2f}. The % of really_close_percentage = {100 * really_close_percentage:.2f}. Average distance: {average_distance:.2f}.") pylab.plot(a, b) # We plot both the percentage of times that the sailor did not venture very far from the pub ... pylab.plot(a, average) #... and his average distance. pylab.show() not_found, search = True, walk_size-1 while not_found: # What is the longest random walk that the sailor could take so that on average he will end up "distancePub" blocks or fewer from the pub? if b[search]<50: search -=1 else: not_found = False print("The solution is: ", a[search], ". The % of really_close_percentage = ", b[search]) if __name__ == '__main__': walk_size(41, 4, 30000)

Walk size = 1.00. The % of really_close_percentage = 100.00. Average distance: 1.00.

[...]
Walk size = 8.00. The % of really_close_percentage = 86.73. Average distance: 3.13.

Walk size = 9.00. The % of really_close_percentage = 67.77. Average distance: 3.31.

Walk size = 10.00. The % of really_close_percentage = 79.33. Average distance: 3.53.

Walk size = 11.00. The % of really_close_percentage = 59.82. Average distance: 3.70.

Walk size = 12.00. The % of really_close_percentage = 73.12. Average distance: 3.87.

Walk size = 13.00. The % of really_close_percentage = 53.83. Average distance: 4.03.

Walk size = 14.00. The % of really_close_percentage = 66.60. Average distance: 4.21.

Walk size = 15.00. The % of really_close_percentage = 48.35. Average distance: 4.35.

Walk size = 16.00. The % of really_close_percentage = 62.54. Average distance: 4.46.

Walk size = 17.00. The % of really_close_percentage = 44.60. Average distance: 4.61.

Walk size = 18.00. The % of really_close_percentage = 58.10. Average distance: 4.74.

Walk size = 19.00. The % of really_close_percentage = 40.89. Average distance: 4.88.

Walk size = 20.00. The % of really_close_percentage = 54.60. Average distance: 5.01.

Walk size = 21.00. The % of really_close_percentage = 37.68. Average distance: 5.17.

Walk size = 22.00. The % of really_close_percentage = 50.52. Average distance: 5.29.

Walk size = 23.00. The % of really_close_percentage = 35.21. Average distance: 5.39.

Walk size = 24.00. The % of really_close_percentage = 47.84. Average distance: 5.52.

[...]
The solution is: 22 . The % of really_close_percentage = 50.519999999999996

He can take 22 steps and he will end up not very far from the pub half of the times. Please observe that the sailor needs to walk quite a lot to get far from the pub and it only get worse as the number of step increases. For instance, to get one block further away from the pub, the drunken sailor needs to increase his walk from 28 steps (Average distance: 6.04) to 39 (Average distance: 7:04).

Compártelo / Share it!