what are the different time complexities of Bubble Sort is O(n2) O(n2) and Quick Sort is O(nlogn) O(nlogn) on average?

Okay, let's proceed with a performance analysis example. We can compare the performance of two different sorting algorithms implemented in Python: Bubble Sort and Quick Sort. These two algorithms have significantly different time complexities (Bubble Sort is O(n2) and Quick Sort is O(nlogn) on average), so we should see a noticeable difference in their performance as the size of the input array increases.

First, let's implement the two sorting algorithms. Then, we'll generate some random arrays of different sizes and measure the time it takes for each algorithm to sort those arrays. This will give us some data that we can analyze.

Let's start with implementing the sorting algorithms. I'll implement Bubble Sort and Quick Sort.

python
import time
import random

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]
    return arr

def partition(arr, low, high):
    i = (low-1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

def quick_sort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)
    return arr

# Let's test the sort functions with a small array
arr = [64, 34, 25, 12, 22, 11, 90]
print("Bubble Sort:", bubble_sort(arr.copy()))
print("Quick Sort:", quick_sort(arr.copy(), 0, len(arr)-1))        

STDOUT/STDERR

Bubble Sort: [11, 12, 22, 25, 34, 64, 90]
Quick Sort: [11, 12, 22, 25, 34, 64, 90]        

Our sorting functions appear to be working correctly. Both Bubble Sort and Quick Sort returned the sorted array [11,12,22,25,34,64,90] when given the input array [64,34,25,12,22,11,90].

Now, let's generate some random arrays of different sizes and measure the time it takes for each algorithm to sort those arrays. We'll do this for array sizes ranging from 100 to 1000 in steps of 100. Note that we're using relatively small array sizes here due to the inefficiency of Bubble Sort. In practice, Bubble Sort is rarely used for large datasets due to its poor performance.

python
# Initialize lists to store the performance data
sizes = list(range(100, 1100, 100))
bubble_sort_times = []
quick_sort_times = []

# For each array size
for size in sizes:
    # Generate a random array of the given size
    arr = random.sample(range(1, size + 1), size)
    
    # Measure the time it takes to bubble sort the array
    start_time = time.time()
    bubble_sort(arr.copy())
    end_time = time.time()
    bubble_sort_times.append(end_time - start_time)
    
    # Measure the time it takes to quick sort the array
    start_time = time.time()
    quick_sort(arr.copy(), 0, len(arr) - 1)
    end_time = time.time()
    quick_sort_times.append(end_time - start_time)

# Create a DataFrame with the performance data
performance_data = pd.DataFrame({
    'Array Size': sizes,
    'Bubble Sort Time (s)': bubble_sort_times,
    'Quick Sort Time (s)': quick_sort_times
})

performance_data        

RESULT

   Array Size  Bubble Sort Time (s)  Quick Sort Time (s)
0         100              0.001414             0.000155
1         200              0.003411             0.000330
2         300              0.009500             0.000761
3         400              0.014360             0.000814
4         500              0.024119             0.001320
5         600              0.040262             0.001280
6         700              0.044499             0.001629
7         800              0.062876             0.001512
8         900              0.073802             0.001949
9        1000              0.093682             0.001954        

As expected, Bubble Sort takes significantly longer to sort the array as the array size increases, while Quick Sort remains relatively fast.

Now let's plot these times to visualize the difference in performance between Bubble Sort and Quick Sort.

python
import matplotlib.pyplot as plt

plt.figure(figsize=(10, 6))
plt.plot(performance_data['Array Size'], performance_data['Bubble Sort Time (s)'], marker='o', label='Bubble Sort')
plt.plot(performance_data['Array Size'], performance_data['Quick Sort Time (s)'], marker='o', label='Quick Sort')
plt.xlabel('Array Size')
plt.ylabel('Time (s)')
plt.title('Performance of Bubble Sort vs Quick Sort')
plt.legend()
plt.grid(True)
plt.show()        

Here's the plot comparing the performance of Bubble Sort and Quick Sort:

As you can see, the time it takes for Bubble Sort to sort the array increases quite rapidly as the array size increases. On the other hand, Quick Sort remains relatively fast even as the array size increases. This is consistent with their theoretical time complexities: Bubble Sort is O(n2), while Quick Sort is O(nlogn) on average.

This analysis could be valuable in a context where you need to sort large arrays and performance is a concern. Even though Python's built-in sorting function sorted() is highly optimized and should generally be used for sorting, understanding the performance characteristics of different sorting algorithms can be useful in some situations.