Introduction

Sorting is one of the most fundamental operations in computer science, and there are various algorithms designed to sort a collection of data. In this tutorial, we will explore three popular sorting algorithms: Bubble Sort, Quick Sort, and Merge Sort. Each of these algorithms has its strengths and weaknesses, and understanding when and how to use them is important for optimizing performance.

The main objective of this exercise is to implement these sorting algorithms in Python and compare their behavior on different sets of data.

Objective

• Implement Bubble Sort, Quick Sort, and Merge Sort algorithms in Python.
• Compare the performance of each sorting algorithm with respect to time complexity and ease of implementation.
• Understand how these algorithms work and when to use each one for different types of data.

Python Code for Sorting Algorithms

# Bubble Sort Implementation
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap elements
    return arr

# Quick Sort Implementation
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Choose the pivot element
    left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Merge Sort Implementation
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[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]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

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

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

    return arr

# Test the Sorting Algorithms
if __name__ == "__main__":
    # Sample input
    sample_data = [64, 34, 25, 12, 22, 11, 90]

    print("Original Array: ", sample_data)

    # Bubble Sort
    print("Bubble Sort: ", bubble_sort(sample_data.copy()))

    # Quick Sort
    print("Quick Sort: ", quick_sort(sample_data.copy()))

    # Merge Sort
    print("Merge Sort: ", merge_sort(sample_data.copy()))

Explanation of the Program

The program consists of three sorting algorithm implementations: Bubble Sort, Quick Sort, and Merge Sort. Let’s break down each section of the program:

• Bubble Sort: This is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until the list is sorted. This algorithm has an average time complexity of O(n²), making it inefficient for large datasets.
• Quick Sort: This is a divide-and-conquer algorithm that divides the list into smaller sub-lists and sorts them recursively. It picks a ‘pivot’ element, partitions the list into elements smaller than the pivot and elements greater than the pivot, and then recursively sorts the sublists. It generally has a time complexity of O(n log n) but can degrade to O(n²) in the worst case.
• Merge Sort: This is also a divide-and-conquer algorithm. It divides the list into two halves, recursively sorts them, and merges the sorted halves back together. Merge Sort has a time complexity of O(n log n) and performs well on large datasets.

How to Run the Program

To run the program:

1. Ensure that you have Python installed on your system.
2. Copy the code into a Python file (e.g., sorting_algorithms.py).
3. Run the Python file from your terminal or command prompt by typing: python sorting_algorithms.py.
4. The program will display the original array and the sorted arrays using Bubble Sort, Quick Sort, and Merge Sort.