Quadratic Sorts

---

Selection Sort

The idea of Selection Sort is that we repeatedly find the smallest element in the list and bring it to the left side.

for i gets the values from 0 to length-2
  min = i
  for j gets the values from i+1 to length-1
    if val[j] < val[min]
      min = j
  swap val[min] and val[i] 
  // at this point, all elements with an index i or smaller are sorted.` 

• In the outer loop of the code, there would have to be a variable keeping track of the index with the smallest element in the unsorted part of the array.

• To find the actual smallest element's index, the inner loop would have to update this variable as it loops through all the elements in the unsorted part of the array.

• Then, a swap between the front of the unsorted part of the array and the smallest element would occur as the last line in the outer loop.

• This pattern continues as the unsorted part of the array becomes smaller and smal

Insertion Sort

In Insertion Sort, we divide the list into two parts, a sorted and an unsorted part. At each iteration, insertion sort removes one element from the unsorted part, finds its location within the sorted part, and inserts it there. It repeats this process until no elements remain in the unsorted part.

for i gets values from 1 to length-1 j gets i while j > 0 and val[j] < val[j-1] swap val[j] and val[j-1] decrement j by 1 // at this point, all elements to the left of index i are sorted.

Bubble Sort

The idea of Selection Sort is that we repeatedly find the smallest element in the list and bring it to the left side.

for i gets the values from last index to 1
  for j gets the values from 0 to i-1
    if val[j] > val[j+1]
      swap val[j] & val[j+1]` 

• The pseudocode does not have the "stop early if no swaps" optimization.