1. Write pseudocode for bubble sort.

FUNCTION bubbleSort(data)
  SET swapped to false

  FOR i = FIRST index of data to LAST index of data - 1
    IF data[i] > data [i + 1]
      SET tmp to data[i]
      set data[i] to data [i+1]
      set data [i+1] to tmp
      set swapped to true
    END IF
  END FOR
  UNTIL swapped is false
  RETURN data
END FUNCTION


2.Write pseudocode for quicksort.

FUNCTION quickSort(array)

  IF (array length < 2)
    RETURN array

  SET pivot to  array[0]

  FOR FIRST index of array to length or array i++
    IF array[i] is less than pivot
      lesser push array[i]
    ELSE
      greater push array [i]
  RETURN quickSort(lesser).concat(pivot,quickSort(greater));
END FUNCTION


3.We talked about time complexity in a previous checkpoint, and how to get an idea
of the efficiency of an algorithm. After looking at the pseudocode for the above
sorting methods, identify why merge sort and quick sort are much more efficient
than the others. Walking through each algorithm with a few sample collections may
help.

Insertion sort must iterate through the entire data set multiple times until the
set is sorted, this makes it a costly process particularly for large data sets.
Selection sort uses a nested for loop, which gives it a time complexity of O(n^2).
With bubble sort, you run the risk of having to make several passes through a large
data set, which also gives the algorithm a time complexity of O(n^2).

Merge sort and quick sort both have time complexities of O(n log (n)). They accomplish
this by only iterating through the entire array once, and then splitting work into
smaller more manageable data sets.

4.All of the sorts addressed in this checkpoint are known as comparison sorts.
Research bucket sort and explain how it works. What is the ideal input for bucket
sort?

Bucket sort separates values into buckets, each bucket is then individually sorted
and finally, the sorted buckets are placed back into an array. The ideal input for
a bucket sort is an array.