Algorithms

Question 1

Binary search iterative

Answer 1

"sorted list
Complexity O(log2n)
Space complexity is o(1)
how many times we have to half n to to reach the target
''

def binary_search(lt, target):
    left_wall=-1
    right_w=len(lt)

    while left_wall guess:
            left_wall=mid
        else :
            return print (lt.index(guess))
    return False

Question 2

Binary search recursive

Answer 2

def binary_search_recursive(list1, element):
    if len(list1) == 0:
        return False
    else:
        mid = len(list1)//2
        if (element == list1[mid]):
            return True
        else:
            if element > list1[mid]:
                return binary_search_recursive(list1[mid+1:],element)
            else:
                return binary_search_recursive(list1[:mid],element)

Question 3

Bubble sort

Answer 3

”””
Worst case scenario is O (n2)

”””

def bubble(list_a):
    indexing_length = len(list_a) - 1 
    sorted = False 

while not sorted:  
    sorted = True  

    for i in range(0, indexing_length): # For every value in the list
        if list_a[i] > list_a[i+1]: 
            sorted = False # These values are unsorted
            list_a[i], list_a[i+1] = list_a[i+1], list_a[i] 
return list_a

Question 4

quick sort

Answer 4

"""
average O(n log n)
space O (logn)

”””

def quick_sort(list):
    if len(list) <=1 :
        return list
    else:
        pivot=list.pop()
        list_greater=[]
        list_smaller=[]
        for item in list:
            if item

Question 5

selection sort

Answer 5

”””
O (n2) time complexity - two loops
o (1) space
select a number , compare to all elem to the right. if we find a smaller value than we replace the min. once
the pass is concluded we move the min to the left most position an continue
“””

def selection(list):
    indexed=range(0,len(list)-1)
    for i in indexed:
        min=i
        for j in range(i+1,len(list)):
            if list[min] >list[j]:
                min=j
        if min != i:
            list[i],list[min]=list[min],list[i]
    return list

Question 6

merge sort

Answer 6

’’’

TIme complexity O(nlogn) : n from merge , logn from cutting the window
Space complexity O(n)
‘’’

def merge_sort(list_to_sort):
    if len(list_to_sort) <=1:
        return list_to_sort
    mid=len(list_to_sort)//2
    left= merge_sort(list_to_sort[:mid])
    right= merge_sort( list_to_sort[mid:])
    print('left',left)
    print('right',right)
    left_pointer=right_pointer=0
    result=[]
    while  left_pointer