Data Structures Python Assignment 1

Student Names

• Names: Amit Postelnik, Shani Kalimi

Selected Algorithms

For this assignment, we implemented and compared the following three sorting algorithms:

1. Algorithm 1: Bubble Sort
2. Algorithm 3: Insertion Sort
3. Algorithm 5: Quick Sort

Experimental Results

1. Random Arrays (result1.png)

Explanation: In this experiment, we used arrays filled with random integers.

• Bubble Sort and Insertion Sort both exhibit quadratic growth $O(n^2)$.
• Quick Sort remains extremely efficient, following its theoretical $O(n \log n)$ complexity.
• The shaded area around each line represents the Standard Deviation (STD), showing the consistency of the algorithm's performance across 5 different trials.

2. Nearly Sorted Arrays - 5% Noise (result2.png)

Explanation: When the array is "Nearly Sorted" (only 5% of elements swapped), we see a dramatic shift:

• Insertion Sort execution time decreases comparing to the random array results, performing almost in linear time $O(n)$. This is because it only needs to perform very few comparisons and shifts.
• Bubble Sort also improves slightly due to the "swapped" flag, which allows it to skip unnecessary passes.

3. Nearly Sorted Arrays - 20% Noise (additional_plots/result_noise20.png)

Explanation: In this additional experiment, we increased the "noise" (disorder) to 20%:

• Result: We can observe that Insertion Sort is still fast, but its runtime starts to climb compared to the 5% case. As more elements are out of place, the algorithm must perform more work to shift them into position.
• Quick Sort remains stable, showing that it is less sensitive to the initial order of elements than the simpler $O(n^2)$ algorithms.

---

How to Run

To reproduce these charts, use these commands in the terminal:

# Random Arrays
python run_experiments.py -a 1 3 5 -s 100 500 1000 3000 5000 -e 0 -r 5

# Nearly Sorted (5% Noise)
python run_experiments.py -a 1 3 5 -s 100 500 1000 3000 5000 -e 1 -r 5

# Nearly Sorted (20% Noise)
python run_experiments.py -a 1 3 5 -s 100 500 1000 3000 5000 -e 2 -r 5