Sorting Methods
CSE2231: Software 2
Sorting Machine
the OSU Components Library has a simple class for sorting algorithms called SortingMachine<T>.
- The Data Type to be sorted is passed as the type of the sorting machine
- the order will be used by a comparator passed in the constructor
- The sorting algorithm comes from the implementation of
SortingMachine<T>
Using Sorting Machines
There are two modes that a SortingMachine<T> can be in. These are insertion mode and extraction mode.
Insertion Mode
While in insertion mode, the SortingMachine<T> will take in elements through the .add(T x) method.
Then it can be switched to extraction mode.
Extraction Mode
When the SortingMachine<T> is in extraction mode, items can be removed from the machine through the .removeFirst() method which will return them in order.
Once a SortingMachine<T> is put into extraction mode, the only way to get it back to insertion mode is to clear it.
Sorting Algorithms
Insertion Sort
Insertion Sort is an eager algorithm (meaning it does work as soon as possible). it adds items one by one to a new list to ensure that they’re sorted.
- Runs in \(O(n^2)\) time, although it can run in linear time in perfect scenario.
Selection Sort
Selection Sort is a lazy algorithm (meaning it does the work at late as possible). It searches an array for the smallest item and then adds them to a sorted list.
- Runs in \(O(n^2)\)