JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Algorithms. Quick, selection, and bubble sort, binary search, merge sort. Random walk.

An algorithm is like a recipe, Muhammad Waseem.

An algorithm is like a recipe, Muhammad Waseem.

An algorithm is a step-by-step procedure, that is, a finite sequence of well-defined instructions for solving problems or accomplishing tasks.

Pygorithm

Pygorithm is a fun way to learn algorithms on the go! We are going to import the bubble_sort algorithm (from pygorithm.sorting import bubble_sort). There are other sorting methods available, such as quick_sort, merge_sort, bubble_sort, etc.

>>> print(bubble_sort.get_code()) # It prints the code for the bubble sort algorithm.
def sort(_list):
    """
    Bubble Sorting algorithm

    :param _list: list of values to sort
    :return: sorted values
    """
    for i in range(len(_list)):
        for j in range(len(_list) - 1, i, -1):
            if _list[j] < _list[j - 1]:
                _list[j], _list[j - 1] = _list[j - 1], _list[j]
    return _list

>>> print(bubble_sort.time_complexities())
# bubble_sort.time_complexities() returns time complexities, i.e., Best Case, Average Case, and Worst Case.
Best Case: O(n), Average Case: O(n ^ 2), Worst Case: O(n ^ 2). 

For Improved Bubble Sort:
Best Case: O(n); Average Case: O(n * (n - 1) / 4); Worst Case: O(n ^ 2)
>>> myList = [3, 2, 1, 7, 8, 4, 5, 6, 9, 12, 22]
>>> print(bubble_sort.sort(myList)) # Let's sort the list.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 22]

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]("/code/programming-fundamentals-algorithms/") 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

Sorting algorithms

Sorting algorithms

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
Visualizing Sorting Algorithms

Visualizing Sorting Algorithms

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.

Merge Sort

Merge Sort

        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
Binary Search

Binary Search

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](https://www.youtube.com/channel/UCW6TXMZ5Pq6yL6_k5NZ2e0Q) (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

Drunken sailor

Drunken sailor

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).

Bitcoin donation

JustToThePoint Copyright © 2011 - 2024 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.