Sorting Algorithms: Insertion, Selection, Bubble Sort

• The text describes three sorting algorithms: insertion sort, selection sort, and bubble sort.

Tri par insertion (Insertion Sort)

• At each step, the next element of the sequence to be sorted is examined and inserted in its place in the already sorted sequence.
• Example: Consider the array | 5 | 2 | 4 | 6 | 1 | 3 |. The algorithm iterates, inserting each element into the correct position within the sorted portion of the array to the left.
• The first element (5) is considered already sorted.
• The second element (2) is inserted: | 2 | 5 | 4 | 6 | 1 | 3 |
• The third element (4) is inserted: | 2 | 4 | 5 | 6 | 1 | 3 |
• The fourth element (6) is inserted: | 2 | 4 | 5 | 6 | 1 | 3 |
• The fifth element (1) is inserted: | 1 | 2 | 4 | 5 | 6 | 3 |
• The sixth element (3) is inserted: | 1 | 2 | 3 | 4 | 5 | 6 |
• Algorithm:

function tri_insertion(tableau T)
  for i from 1 to length(T) - 1 do
    valeur := T[i]
    j := i
    while j > 0 and T[j-1] > valeur do
      T[j] := T[j-1]
      j := j - 1
    end while
    T[j] := valeur
  end for
end function

• The complexity is $O(n^2)$ in the worst case, and $O(n)$ in the best case.

Tri par sélection (Selection Sort)

• The smallest element of the array is searched for and placed in the first position, next the smallest element of the rest of the array is placed in the second position, and so on.
• Example: Given the array | 5 | 2 | 4 | 6 | 1 | 3 |.
• Find the smallest element (1) and exchange it with the first element (5): | 1 | 2 | 4 | 6 | 5 | 3 |
• Find the smallest element of the remaining array (2) and exchange it with the second element (2): | 1 | 2 | 4 | 6 | 5 | 3 |
• Find the smallest element of the remaining array (3) and exchange it with the third element (4): | 1 | 2 | 3 | 6 | 5 | 4 |
• Find the smallest element of the remaining array (4) and exchange it with the fourth element (6): | 1 | 2 | 3 | 4 | 5 | 6 |
• Find the smallest element of the remaining array (5) and exchange it with the fifth element (5): | 1 | 2 | 3 | 4 | 5 | 6 |
• Algorithm:

Function tri_selection(tableau T)
  for i from 0 to length(T) - 2 do
    min := i
    for j from i + 1 to length(T) - 1 do
      if T[j] < T[min] then
        min := j
      end if
    end for
    if min != i then
      echanger(T[i], T[min])
    end if
  end for
Fin function

• The complexity of selection sort is $O(n^2)$ in all cases.

Tri à bulles (Bubble Sort)

• The array is traversed, comparing adjacent elements. If they are incorrectly sorted, they are exchanged. The operation is repeated until there are no more exchanges.
• Example: Given the array | 5 | 2 | 4 | 6 | 1 | 3 |.
• Traverse the array and swap adjacent elements if they are out of order.
• 5 and 2 are out of order: | 2 | 5 | 4 | 6 | 1 | 3 |
• 5 and 4 are out of order: | 2 | 4 | 5 | 6 | 1 | 3 |
• 5 and 6 are in order.
• 6 and 1 are out of order: | 2 | 4 | 5 | 1 | 6 | 3 |
• 6 and 3 are out of order: | 2 | 4 | 5 | 1 | 3 | 6 |
• Repeat the operation:
• 2 and 4 are in order.
• 4 and 5 are in order.
• 5 and 1 are out of order: | 2 | 4 | 1 | 5 | 3 | 6 |
• 5 and 3 are out of order: | 2 | 4 | 1 | 3 | 5 | 6 |
• 5 and 6 are in order.
• Repeat the operation, and so on, until the array is sorted: | 1 | 2 | 3 | 4 | 5 | 6 |
• Algorithm:

Fonction tri_bulle(tableau T)
  repeat
    echange := faux
    for i from 0 to length(T) - 2 do
      if T[i] > T[i+1] then
        echanger(T[i], T[i+1])
        echange := vrai
      end if
    end for
  tant que echange
Fin function

• The complexity of bubble sort is $O(n^2)$ in the worst case and $O(n)$ in the best case.