By the end of this chapter, you will learn about the types of algorithm attributes and various types of algorithms designed for specific purposes. You will be introduced to terms such as the order of magnitude and you will learn how this measurement is used to classify algorithms.
Correctness -This is a major attribute as the algorithm defeats its purpose if it cannot yield correct results
Does the algorithm yield correct results?
Does it finish what it was intended to do?
Ask these questions to test the correctness of an algorithm
Clarity - How easy the algorithm is understood
If an algorithm is ambiguous and hard to understand, then it lacks clarity
Elegance - Essentially the style of your algorithm (how it solves the problem)
Elegance usually comes in conflict with clarity
Efficiency - How much memory the algorithm takes up
How well does the algorithm utilize the resources given?
Does the algorithm take a long time to execute or does it take up too much storage?
Ask these questions to determine efficiency
Benchmarking (Not an attribute) - How different inputs can affect the time the algorithm takes to yield results
Sequential Search
Comparing the wanted value with every value in the given list
If the list is n numbers long, 1 is the best case, n is the worst case, and n/2 is the average case
Order of Magnitude - Order n
If n is the length of a list, then the order of mangnitude varies based on the value of n
Selection Sort
A marker splits a list into unsorted and sorted sections (marker starts on the end of the list at the beginning so there is no sorted section yet)
Then, the largest value in the unsorted list is found and it is switched with the last number in the unsorted section of the list (to the left of the marker)
The marker then moves passed the largest value that was just switched (that number is now in the sorted section of the list)
Order of Magnitude - Order n^2
An example of an order of magnitude of n^2 is the selection sort algorithm as it does not simply follow the pattern of n.
Data Cleanup Algorithms
Data Cleanup Algorithms seek to remove values in a list that do not make sense
The Shuffle-Left Algorithm
Put left pointer finger at the start of the list and right at the second number on the list. Move the right finger down the list and keeping going until a zero or a value that does not make sense is reached. If a zero is reached, everything to the left of the zero is moved left 1 cell. The right finger resets once the whole list is scanned and the process repeats.
The Copy-Over Algorithm
The list looks from left to right and transfers all non zero digits to a second list. This takes up a lot of space because the orignial list remains and the new list is also created.
The Converging-Pointers Algorithm
A pointer is placed at the beginning and at the end of the list. The left pointer the list for not legitimate numbers. When a not legitimate number is reached, the number at the right pointer is copied to the left pointer. Then, the right pointer moves right one space.
Binary Search
Requires a sorted list. The number in the middle of the list is checked and if it is equal to the number that is being searched, then the algorithm stops. However, if the middle number is not equal to the middle number of the list, the algorithm checks if the middle number is higher or lower than the number being searched. If the number being searched is lower than the middle number, then the list is will be searched at the lower half. The opposite applies if the number being searched is higher than the middle number.
Pattern Matching
The algorithm scans the text and tries to match patterns in the list with the pattern that needs to be found. The number of comparisons is determined by the expression n-m+1
Note: Check the chart on page 131 of the textbook for the order of magnitudes of each type of algorithm.