Insertion Sort and Binary Search

Videos:

Insertion Sort Code:

import time
def insertionSort(arr):
 
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
 
        key = arr[i]
 
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
        time.sleep(0.5)
        print(arr)
 
 
# Driver code to test above
a = int(input("Enter a number:"))
b = int(input("Enter a number:"))
c = int(input("Enter a number:"))
d = int(input("Enter a number:"))
e = int(input("Enter a number:"))

arr = [a, b, c, d, e]
insertionSort(arr)
time.sleep(1)
print ("Sorted array is:")
print(arr)

Binary search code:
def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            print("Your number was found")
            break
        elif target > val:
            if lower == x:   # this two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x
a = int(input("Please enter a number between 1 and 10:"))
binary_search([1,5,8,10], a)

In insertion sort, the code looks through the numbers and recognises whether a number is larger or smaller than previously checked numbers. This sorting method actually looks at all previously checked numbers instead of just the previous one. Insertion sort inserts a number where it fits. 

Binary search is an effective search method which uses a middle number to search for another number. In binary search, the middle element in the array is compared to the number that needs to be found. If the number is bigger, then the middle number and everything smaller is removed, but if it is smaller, the middle number and everything bigger is removed. This process is continued until the number is found.

Sources:

Binary Search Code: https://stackoverflow.com/questions/9501337/binary-search-algorithm-in-python

Insertion Sort Code: https://www.geeksforgeeks.org/insertion-sort/

How does insertion sort work: https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort

How does Binary Search work: https://www.youtube.com/watch?v=JQhciTuD3E8

Leave a Reply

Your email address will not be published. Required fields are marked *