Year after year

• Below are some common sorting algorithms used in computer science.

Insertion Sort

• Array sorting is analogous to sorting a hand of playing cards.
• The algorithm iterates through the array, inserting each element into its correct sorted position within the preceding subarray.
• The tri_insertion function in Python implements this algorithm.
• It iterates from the second element to the last, comparing each element with those before it and shifting larger elements to the right to make space for insertion.

Insertion Sort Complexity

• Worst-case comparisons: $O(n^2)$
• Best-case comparisons: $O(n)$
• Assignments: $O(n^2)$

Selection Sort

• Involves repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning.
• The algorithm searches for the minimum element's index imin in the subarray tab[i..n-1] and swaps tab[i] with tab[imin].
• The tri_selection function in Python does this process.

Selection Sort Complexity

• Comparisons: $O(n^2)$
• Assignments: $O(n)$

Bubble Sort

• Works by repeatedly stepping through the array, comparing adjacent elements and swapping them if they are in the wrong order.
• Larger elements "bubble" to the end of the array with each pass.
• The tri_bulles function in Python implements this.
• The outer loop iterates from the end of the array to the beginning, and the inner loop compares and swaps adjacent elements.

Bubble Sort Complexity

• Worst-case comparisons: $O(n^2)$
• Best-case comparisons: $O(n)$
• Assignments: $O(n^2)$

Quick Sort

• Employs a "divide and conquer" strategy.
• A pivot element is chosen, and the array is partitioned into two sub-arrays.
• Elements less than the pivot are moved before it, and elements greater than the pivot are moved after it.
• The sub-arrays are then recursively sorted.
• The partition function rearranges the array around the pivot.
• The tri_rapide function recursively sorts the sub-arrays.

Quick Sort Complexity

• Average and best-case: $O(n \log n)$
• Worst-case: $O(n^2)$

Merge Sort

• Another "divide and conquer" algorithm.
• The array is divided into two halves, which are recursively sorted, and then merged.
• The tri_fusion function in Python recursively divides the array until it reaches individual elements, then merges them back in sorted order.

Merge Sort Complexity

• Complexity: $O(n \log n)$