problem3.py

problem = "problem3"
student_name = "Abudi Alshamam"
student_numer = "N1212353"

"""
source of bubble sort, selection sort and mrge sort code:
@author: ericgrimson
"""

import random

num_comparisson = 0

def bubble_sort(L):
    global num_comparisson
    num_comparisson = 0
    swap = False
    while not swap:
        swap = True
        for j in range(1, len(L)):
            if L[j-1] > L[j]:
                num_comparisson += 1
                swap = False
                temp = L[j]
                L[j] = L[j-1]
                L[j-1] = temp
      
def selection_sort(L):
    global num_comparisson
    num_comparisson = 0
    suffixSt = 0
    while suffixSt != len(L):
        for i in range(suffixSt, len(L)):
            if L[i] < L[suffixSt]:
                num_comparisson += 1
                L[suffixSt], L[i] = L[i], L[suffixSt]
        suffixSt += 1

def merge(left, right):
    global num_comparisson
    result = []
    i,j = 0,0
    while i < len(left) and j < len(right):
        num_comparisson += 1
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        num_comparisson += 1
        result.append(left[i])
        i += 1
    while (j < len(right)):
        num_comparisson += 1
        result.append(right[j])
        j += 1
    return result

def merge_sort(L):
    global num_comparisson
    num_comparisson = 0
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        left = merge_sort(L[:middle])
        right = merge_sort(L[middle:])
        return merge(left, right)
        
def sort_comparison(list_size, sorted=False):
    global num_comparisson
    sort_list = [random.randint(0, 100) for i in range(list_size)]
    print('List of size ' + str(list_size) + ' to sort is: ' + str(sort_list))
    
    bubble_sort(sort_list[:])
    print(f'Number of comparisons for bubble sort: {num_comparisson}')

    
    selection_sort(sort_list[:])
    print(f'Number of comparisons for selection sort: {num_comparisson}')

    
    merge_sort(sort_list[:])
    print(f'Number of comparisons for merge sort: {num_comparisson}')

sort_comparison(20)