Practice examples: algorithms and implementations

Provide a function to implement each of the following algorithms:

  1. Euclid's algorithm for GCD
    Objective: given two numbers, X and Y, find their greatest common
       divisor (GCD) i.e. the largest number that evenly divides both
    
    Algorithm
       put the larger of values X and Y in L,
           and the other value in S
       repeat until S is 0:
          store a copy of S
          divide L by S, putting the remainder in S
          replace L with the stored copy of S 
       once the loop completes, L contains the gcd of X and Y
    

  2. Bubblesort sorting algorithm
    Objective: given an array, A, of N numbers,
       sort the numbers in N in non-decreasing order
       (i.e. smaller numbers at the front, larger at the back)
    
    Algorithm:
       repeat N times:
          for positions p=0 through N-2
              if element p < element p+1
                 swap the two elements
    

  3. Selection sort algorithm
    Objective: given an array, A, of N numbers,
       sort the numbers in N in non-decreasing order
       (i.e. smaller numbers at the front, larger at the back)
    
    Algorithm:
       for positions p=0 through N-1
           find the smallest value in positions p+1 through N-1
              remembering which position, t, it is in
           swap the value in position p with the value in position t