Basic Python Programs: Sorting - Computational Physics Formulation & Simulation

Program 1

Sorting

Python 3.11 Ready

Click "Run Code" to execute script and render figures.

Mathematical Problem Formulation

Bubble Sort

Initial Array

[6, 2, 9, 0, 1, 5, 8, 7]

Step-by-Step Process

First Pass:

Compare $6$ and $2$:

$6 > 2$ ? Swap ? [2, 6, 9, 0, 1, 5, 8, 7]

Compare $6$ and $9$:

$6 < 9$ ? No swap ? [2, 6, 9, 0, 1, 5, 8, 7]

Compare $9$ and $0$:

$9 > 0$ ? Swap ? [2, 6, 0, 9, 1, 5, 8, 7]

Compare $9$ and $1$:

$9 > 1$ ? Swap ? [2, 6, 0, 1, 9, 5, 8, 7]

Compare $9$ and $5$:

$9 > 5$ ? Swap ? [2, 6, 0, 1, 5, 9, 8, 7]

Compare $9$ and $8$:

$9 > 8$ ? Swap ? [2, 6, 0, 1, 5, 8, 9, 7]

Compare $9$ and $7$:

$9 > 7$ ? Swap ? [2, 6, 0, 1, 5, 8, 7, 9]

End of First Pass: Largest element $9$ has bubbled to the last position.

Array after first pass: [2, 6, 0, 1, 5, 8, 7, 9]

Second Pass:

Compare $2$ and $6$:

$2 < 6$ ? No swap ? [2, 6, 0, 1, 5, 8, 7, 9]

Compare $6$ and $0$:

$6 > 0$ ? Swap ? [2, 0, 6, 1, 5, 8, 7, 9]

Compare $6$ and $1$:

$6 > 1$ ? Swap ? [2, 0, 1, 6, 5, 8, 7, 9]

Compare $6$ and $5$:

$6 > 5$ ? Swap ? [2, 0, 1, 5, 6, 8, 7, 9]

Compare $6$ and $8$:

$6 < 8$ ? No swap ? [2, 0, 1, 5, 6, 8, 7, 9]

Compare $8$ and $7$:

$8 > 7$ ? Swap ? [2, 0, 1, 5, 6, 7, 8, 9]

End of Second Pass: Largest element $8$ is now in its correct position.

Array after second pass: [2, 0, 1, 5, 6, 7, 8, 9]

Third Pass:

Compare $2$ and $0$:

$2 > 0$ ? Swap ? [0, 2, 1, 5, 6, 7, 8, 9]

Compare $2$ and $1$:

$2 > 1$ ? Swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $2$ and $5$:

$2 < 5$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $5$ and $6$:

$5 < 6$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $6$ and $7$:

$6 < 7$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

End of Third Pass: The next largest element $7$ is now in its correct position.

Array after third pass: [0, 1, 2, 5, 6, 7, 8, 9]

Fourth Pass:

Compare $0$ and $1$:

$0 < 1$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $1$ and $2$:

$1 < 2$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $2$ and $5$:

$2 < 5$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $5$ and $6$:

$5 < 6$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare $6$ and $7$:

$6 < 7$ ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

End of Fourth Pass: The array remains sorted, indicating that sorting is complete.

Array after fourth pass: [0, 1, 2, 5, 6, 7, 8, 9]

Program 2

Sorting

Python 3.11 Ready

Click "Run Code" to execute script and render figures.

Program 3

Sorting

Python 3.11 Ready

Click "Run Code" to execute script and render figures.

Mathematical Problem Formulation

Selection Sort

The input array is

[2, 6, 5, 1, 3, 4]

The outer loop will iterate over each index of the array except the last one, as it will already be sorted after the previous iterations.

First Pass (i = 0):

Current Minimum Index (cm): $0$ (pointing to $2$)

Inner Loop:

Compare $6$ with $2$: No change (2 remains the minimum).

Compare $5$ with $2$: No change (2 remains the minimum).

Compare $1$ with $2$: $1 < 2$ ? Update cm to $3$ (pointing to $1$).

Compare $3$ with $1$: No change (1 remains the minimum).

Compare $4$ with $1$: No change (1 remains the minimum).

Swap: Swap the element at index $0$ with the element at index $3$.

Array After First Pass: [1, 6, 5, 2, 3, 4]

Second Pass (i = 1):

Current Minimum Index (cm): $1$ (pointing to $6$)

Inner Loop:

Compare $5$ with $6$: $5 < 6$ ? Update cm to $2$ (pointing to $5$).

Compare $2$ with $5$: $2 < 5$ ? Update cm to $3$ (pointing to $2$).

Compare $3$ with $2$: No change (2 remains the minimum).

Compare $4$ with $2$: No change (2 remains the minimum).

Swap: Swap the element at index $1$ with the element at index $3$.

Array After Second Pass: [1, 2, 5, 6, 3, 4]

Third Pass (i = 2):

Current Minimum Index (cm): $2$ (pointing to $5$)

Inner Loop:

Compare $6$ with $5$: No change (5 remains the minimum).

Compare $3$ with $5$: $3 < 5$ ? Update cm to $4$ (pointing to $3$).

Compare $4$ with $3$: No change (3 remains the minimum).

Swap: Swap the element at index $2$ with the element at index $4$.

Array After Third Pass: [1, 2, 3, 6, 5, 4]

Fourth Pass (i = 3):

Current Minimum Index (cm): $3$ (pointing to $6$)

Inner Loop:

Compare $5$ with $6$: $5 < 6$ ? Update cm to $4$ (pointing to $5$).

Compare $4$ with $5$: $4 < 5$ ? Update cm to $5$ (pointing to $4$).

Swap: Swap the element at index $3$ with the element at index $5$.

Array After Fourth Pass: [1, 2, 3, 4, 5, 6]

Fifth Pass (i = 4):

Current Minimum Index (cm): $4$ (pointing to $5$)

Inner Loop:

Compare $6$ with $5$: No change (5 remains the minimum).

No Swap Needed: Since cm is still $4$, the array remains the same.

Array After Fifth Pass: [1, 2, 3, 4, 5, 6]

Program 4

Sorting

Python 3.11 Ready

Click "Run Code" to execute script and render figures.

Mathematical Problem Formulation

Insertion Sort:

Initial Array

Input Array:

[2, 6, 5, 1, 3, 4]

Algorithm Explanation

Insertion sort works by building a sorted portion of the array one element at a time. It takes each element from the unsorted part and finds its correct position in the sorted part.

Step-by-Step Process

Initialization:

The input array is [2, 6, 5, 1, 3, 4]. The outer loop starts at index $1$ (the second element), treating the first element as a sorted list of one element.

First Pass (i = 1):

Current Element: $6$

Comparison:

Compare $6$ with $2$ (the element before it):

2 < 6: No swap needed.

Array After First Pass:

[2, 6, 5, 1, 3, 4]

Second Pass (i = 2):

Current Element: $5$

Comparison:

Compare $5$ with $6$:

6 > 5: Swap ? [2, 5, 6, 1, 3, 4]

Now compare $5$ with $2$:

2 < 5: No swap needed.

Array After Second Pass:

[2, 5, 6, 1, 3, 4]

Third Pass (i = 3):

Current Element: $1$

Comparison:

Compare $1$ with $6$:

6 > 1: Swap ? [2, 5, 1, 6, 3, 4]

Compare $1$ with $5$:

5 > 1: Swap ? [2, 1, 5, 6, 3, 4]

Compare $1$ with $2$:

2 > 1: Swap ? [1, 2, 5, 6, 3, 4]

Array After Third Pass:

[1, 2, 5, 6, 3, 4]

Fourth Pass (i = 4):

Current Element: $3$

Comparison:

Compare $3$ with $6$:

6 > 3: Swap ? [1, 2, 5, 3, 6, 4]

Compare $3$ with $5$:

5 > 3: Swap ? [1, 2, 3, 5, 6, 4]

Compare $3$ with $2$:

2 < 3: No swap needed.

Array After Fourth Pass:

[1, 2, 3, 5, 6, 4]

Fifth Pass (i = 5):

Current Element: $4$

Comparison:

Compare $4$ with $6$:

6 > 4: Swap ? [1, 2, 3, 5, 4, 6]

Compare $4$ with $5$:

5 > 4: Swap ? [1, 2, 3, 4, 5, 6]

Compare $4$ with $3$:

3 < 4: No swap needed.

Array After Fifth Pass:

[1, 2, 3, 4, 5, 6]

Theoretical Principles & Computational Physics Guide

Sorting Algorithms: Array Ranking & Experimental Data Organization

Dr. Alorika Chatterjee & Dr. Anirban Shaw Science & Physics Learners Python 3 / NumPy / SciPy

1. Core Principles & Theoretical Framework

Order & Efficiency: Reorganizes experimental arrays in ascending or descending order for percentile analysis, median filtering, and fast binary searching.

Algorithmic Hierarchy: Compares quadratic methods (Bubble, Insertion $\mathcal{O}(N^2)$) with divide-and-conquer schemes (Merge, Quick Sort $\mathcal{O}(N \log N)$).

Physical Applications: Essential in particle simulations for spatial cell binning and energy level ranking.

2. Mathematical Formulation & Algorithmic Pipeline

Comparison of sorting time complexity bounds:

$$ T_{\text{Bubble}}(N) \in \mathcal{O}(N^2), \quad T_{\text{Merge}}(N) = 2T(N/2) + \mathcal{O}(N) \implies \mathcal{O}(N \log N) $$

3. Numerical Mechanics & Implementation Logic

Bubble Sort: Iterate through array, swapping adjacent inverted pairs; stop when a complete pass requires zero swaps.
Python Timsort: Python's built-in .sort() employs an adaptive merge-insertion hybrid with $\mathcal{O}(N \log N)$ worst-case.
Coordinate Synchronization: When sorting physical coordinates, ensure corresponding physical arrays (velocities, energies) are permuted in tandem.

4. Relevant Computational Practice Exercises

Exercise 1

Implement Bubble Sort and count the exact number of swaps needed to sort an array of 50 randomized energy values.

Exercise 2

Write a Quick Sort function using the median-of-three pivot selection strategy.

Exercise 3

Sort experimental measurement points $(x_i, y_i)$ by ascending $x$-coordinate while maintaining exact $(x, y)$ pairing.

Standard Literature & References:

Donald E. Knuth, "The Art of Computer Programming, Vol. 3: Sorting and Searching", Addison-Wesley (1998).

Ch. 3.6 Sorting

Sorting

Mathematical Problem Formulation

Bubble Sort

Initial Array

Step-by-Step Process

First Pass:

Second Pass:

Third Pass:

Fourth Pass:

Sorting

Sorting

Mathematical Problem Formulation

Selection Sort

The input array is

First Pass (i = 0):

Inner Loop:

Second Pass (i = 1):

Inner Loop:

Third Pass (i = 2):

Inner Loop:

Fourth Pass (i = 3):

Inner Loop:

Fifth Pass (i = 4):

Inner Loop:

Sorting

Mathematical Problem Formulation

Insertion Sort:

Initial Array

Algorithm Explanation

Step-by-Step Process

Initialization:

First Pass (i = 1):

Second Pass (i = 2):

Third Pass (i = 3):

Fourth Pass (i = 4):

Fifth Pass (i = 5):

1. Core Principles & Theoretical Framework

2. Mathematical Formulation & Algorithmic Pipeline

3. Numerical Mechanics & Implementation Logic

4. Relevant Computational Practice Exercises