Algorithms with Python - Part 2

Refer this article for Algorithms with Python - Part 1.

• Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides a data structure into smaller sub-collections, sorts them, and then merges the sorted sub-parts to produce a final sorted data structure.

Merge sort can be implemented using recursion. Let’s implement a merge sort algorithm to sort an unsorted list of square numbers. We have defined the merge_sort function to take a data structure (list) as its parameter. We use this function recursively to split the left half and the right half of the list until a list reaches the base case of len(list) > 1. Merging is done with the help of three while loops.

Firstly, we split the original list into two sub lists (left_half and right_half) from the first element to the mid element (left_half) and from the mid element to the last element (right_half). Then we make recursive calls to the merge_sort function by passing these sub lists iteratively. The three variables i, j, and k will be used as indices of these three lists for the while loops.

The first while loop is used to traverse through the sub lists till reaching the end of either of them. Inside the loop, we have used an if-else statement to compare the left and right halves’ elements. If the left half has the smaller element, it will be updated to the original list. Else, the element at right half will be updated to the original list. The second and third while loops are used to update any remaining elements from the left half and the right half to the original list respectively in scenarios where the two sub lists are of different lengths.

def merge_sort(list):
    if len(list) > 1:
        mid = len(list) // 2
        left_half = list[:mid]
        right_half = list[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                list[k] = left_half[i]
                i += 1
            else:
                list[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            list[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            list[k] = right_half[j]
            j += 1
            k += 1

list = [100, 64, 81, 1, 25, 16, 4, 49, 9, 36]
merge_sort(list)
print(list)

• Quick Sort

Quick sort is another divide-and-conquer algorithm. Let’s implement a quick sort algorithm to sort the same square numbers list from the above example. The quick_sort function has a base case of len(list) <= 1. We define the variable pivot to be used to create sub lists; left is the sub list that contains elements smaller than the pivot element and right is the sub list that contains elements greater than the pivot element. The middle list contains elements that are the same as the pivot. Then we recursively call the function with left and right lists and merge them with the middle list. This eventually returns the sorted list.

def quick_sort(list):
    if len(list) <= 1:
        return list

    pivot = list[len(list) // 2]
    left = [x for x in list if x < pivot]
    middle = [x for x in list if x == pivot]
    right = [x for x in list if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


list = [100, 64, 81, 1, 25, 16, 4, 49, 9, 36]
sorted_list = quick_sort(list)
print(sorted_list)

Comparison

In conclusion, each sorting algorithm has its own strengths and weaknesses. Selection sort and bubble sort are simple to implement but, not efficient for large datasets. Insertion sort performs well on small lists. Merge sort and quick sort are more efficient for larger datasets, with merge sort being stable and quick sort having better memory efficiency.

Choosing the right sorting algorithm depends on the specific requirements of our task and the size of our dataset. Understanding these algorithms helps us make informed decisions when it comes to working with data.

Algorithm	Time Complexity	Space Complexity	Sorting in-Place	Stable
Selection Sort	O($n^2$)	O($1$)	Yes	No
Bubble Sort	O($n^2$)	O($1$)	Yes	Yes
Insertion Sort	O($n^2$)	O($1$)	Yes	Yes
Merge Sort	O($n$ $log$ $n$)	O($n$)	No	Yes
Quick Sort	O($n^2$)	O($log$ $n$)	Yes	No