Sorting algorithms §

= an ⚙️ Algorithm for sorting e.g. an 🖇 Array (programming)

Algorithms §

• Random sort:
  1. check if list = sorted
  2. Randomly permute(sort) the list
  3. repeat 1 if list != sorted
  • → N! complexity
• Selection sort:
  1. start at first element, compare to all other elements
  2. if there is a smaller element, swap the current element with it
  3. continue until end
     • recursive: call function again without first element
     • iterative: repeat loop at next element using loop counter
• Bucket sort:
  1. create an array with a spot for each possible value
  2. iterate through elements, add 1 to each corresponding spot in the array
  3. iterate through array, return corresponding element(s) for each spot

Recursive Algorithms §

• Quick sort (O(n log n) - O(n^2)):
  1. Termination check: isSorted, array > 1?
  2. Identify pivot element, swap elements from left/right side to the other one if it’s smaller/bigger than the pivot
  3. Repeat recursively for each side