# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Solutions for Sorting Algorithms Exercises

# **Question 1**
#
# Sort the numbers below by using Bubble Sort algorithm.
#
# Make a function called `BubbleSort` which takes argument of a list of numbers.
# Then, display the results of the sorted numbers.
# Find the processing time of this algorithm.
#
# The list of numbers are as below.
#
# `numbers = [56, 3, 1, 78, 24, 45, 67, 99, 35]`

# This solution is taken from https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-4.php

# +
def BubbleSort(numbers):
    lengthOfNumbers = len (numbers) - 1
    for i in range (lengthOfNumbers):
        for j in range (lengthOfNumbers - i):
            if numbers[j] > numbers [j+1]:
                numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
    return numbers

numbers = [56, 3, 1, 78, 24, 45, 67, 99, 35]
sorted_numbers = BubbleSort(numbers)
# %timeit sorted_numbers
print(sorted_numbers)


# -

# **Question 2**
#
# By using the same list of numbers as in Question 1, please write a `MergeSort` function, sort the numbers using merge sort algorithm, display the sorted numbers and display the processing time of this algorithm.

# This solution is taken from https://www.simplifiedpython.net/merge-sort-python/

# +
# Define definition for merge which basically takes two arrays i.e., the left and right part
def merge(left, right):
    result = []  # final result array, that is an empty array
     #create two indices and initialize with 0
    i,j = 0,0
     # Till this condition is true, keep on appending elements into resultant array
    while i<len(left) and j<len(right):
        if left[i] <= right[j]:
            result.append(left[i]) #append ith element of left into resultant array
            i+=1
        else:
            result.append(right[j])  #append jth element of right into resultant array
            j+=1
     # it is basically specifies that if any element is remaining in the left array from -
    # ith to the last index so that it should appended into the resultant array. And similar -
    # to the right array.
    result += left[i:]
    result += right[j:]
    return result
 
# Definition for merge sort
# this takes an input list
def MergeSort(lst):
    if(len(lst)<= 1): # this means that the list is already sorted.
        return lst
    mid = int(len(lst)/2)
     # left array will be mergesort applied over the list from starting index 
    # till the mid index
    left = MergeSort(lst[:mid])
     # right array will be mergesort applied recursively over the list from mid index
    # till the last index 
    right = MergeSort(lst[mid:])
 
    return merge(left,right)  # finally return merge over left and right


numbers = [56, 3, 1, 78, 24, 45, 67, 99, 35]
sorted_numbers = MergeSort(numbers)
# %timeit sorted_numbers
print(sorted_numbers)

# -

# **Question 3**
#
# By using the same list of numbers as in Question 1, please write a `QuickSort` function, sort the numbers using quick sort algorithm, display the sorted numbers and display the processing time of this algorithm.

# Solution is taken from https://www.codementor.io/garethdwyer/quicksort-tutorial-python-https://tutorialedge.net/compsci/sorting/quicksort-in-python/

# +
def QuickSort(array):

    # We define our 3 arrays
    less = []
    equal = []
    greater = []

    # if the length of our array is greater than 1
    # we perform a sort
    if len(array) > 1:
        # Select our pivot. This doesn't have to be
        # the first element of our array
        pivot = array[0]

        # recursively go through every element
        # of the array passed in and sort appropriately
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)

        # recursively call quicksort on gradually smaller and smaller
        # arrays until we have a sorted list.
        return QuickSort(less)+equal+QuickSort(greater)

    else:
        return array
    
numbers = [56, 3, 1, 78, 24, 45, 67, 99, 35]
sorted_numbers = QuickSort(numbers)
# %timeit sorted_numbers
print(sorted_numbers)
# -



StarcoderdataJupyterScriptsDedupFiltered