Homework $6$: Quadratic sorting algorithms

Part $1$: Implementing Recursive Sorting Algorithms

In this part of the homework, you will implement three sorting algorithms: bubble sort, selection sort, and

insertion sort, recursively. Each sorting algorithm should return the sorted array and the number of swaps

made during the sorting process. Your implementation should aim to be as efficient as possible, with no

unnecessary comparison steps and no swaps if not needed. Additionally, you should ensure that both bubble

sort and insertion sort maintain $O(n)$ time complexity in the best case.

Example on number of swaps:$$ sorted$\_$arr, n$\_$swaps $=$ bubble$\_$sort$($sort$\_$list$)$

$$ print$($n$\_$swaps$)$

$0$

$$ rev$\_$sorted for $i$ in range $(5,0,-1)$

$$ sorted$\_$arr, n$\_$swaps $=$ bubble$\_$sort$($rev$\_$sorted$)$

$$ print$($n$\_$swaps$)$

$10$

$$ random$\_$list $=[3,2,5,1,4]$

$>$ sorted$\_$arr, n$\_$swaps $=$ bubble$\_$sort $($random$\_$list$)$

$$ print$($n$\_$swaps$)$

$5$

Part $2$: Building Test Factory for Sorting Algorithms

In this part of the homework, you will build a test factory to test the recursive sorting algorithms implemented

in Part $1.$ The test factory should include test cases for an empty list, a sorted list, a reverse sorted list, and a

randomly shuffled list. By using a test factory, you can avoid repeating the same tests for different sorting

algorithms.