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:

$$ s sort$\_$list for i in range$(5)]$

$$ sorted$\_$arr, $n_{-}$swaps $=$ bubble$\_$sort $($sort$\_$list$)$

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

$$

$$ rev$\_$sorted i 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

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.

$\frac{1}{2}$

hw$6.$md

$2024-02-26$

Below is a graphical representation of how to structure the test factory:

class SortingTestFactory

is$\_$sorted$($self$,$ L$)$

Below is a graphical representation of how to structure the test factory:

A test factory is a design pattern commonly used in software testing to streamline the creation of test cases and promote code reuse. It encapsulates the logic for generating test cases, making it easier to manage and maintain test suites, especially when dealing with multiple test scenarios or similar tests for different functions or classes.

In the context of sorting algorithms, a test factory can be particularly useful for generating test cases to verify the correctness and performance of different sorting implementations. Instead of manually writing test cases for each sorting algorithm, a test factory allows us to define common test scenarios $($e$.$g$.$ empty list, sorted list, reverse sorted list, random list$)$ once and reuse them across multiple sorting algorithms.

class TestInsertion

setUp $($self$)$

A test factory is a design pattern commonly used in software testing to streamline the creation of test cases and promote code reuse. It encapsulates the logic for generating test cases, making it easier to manage and maintain test suites, especially when dealing with multiple test scenarios or similar tests for different functions or classes.

In the context of sorting algorithms, a test factory can be particularly useful for generating test cases to verify the correctness and performance of different sorting implementations. Instead of manually writing test cases for each sorting algorithm, a test factory allows us to define common test scenarios $($e$.$g$.,$ empty list, sorted list, reverse sorted list, random list$)$ once and reuse them across multiple sorting algorithms.

It's important to note that when using a test factory, certain test cases may need to be overridden or modified for specific classes or functions. For example, in the case of sorting algorithms like bubble sort and insertion sort, the test cases may be similar. However, for algorithms like selection sort, which works differently, some test cases in the TestSelection class may need to be overridden or adapted to accommodate these differences. This ensures that the test cases accurately reflect the behavior of each sorting algorithm being tested.

Submission

Submit the following files:

hw$6.$py

test$\_$hw$6.$py

Students must submit to Gradescope individually by the due date $($typically Tuesday at $11$:$59$ pm EST$)$ to receive credit.

$\frac{2}{2}$