Algorithms Flashcards
What does it mean for an algorithm to be “stable”, as opposed to “non-stable”?
A stable algorithm is one that preserves the relative order of the items with equal sort keys.
For example, let’s say we wanted to sort a list of strings, and we have two strings that start with s.
A stable algorithm is one that, no matter how many times the algorithm is repeated, those two strings will always be in the same order.
Stable algorithms tend to be more efficient, and make it easier to implement multikey sorts.
What is the general process for a selection sort algorithm?
We first go to the end of the list, then find the largest element.
That largest element is then put at the end of the list. After this, we call selection sort again on the rest of the list, until we reach the base case.
What is the order of a selection sort algorithm?
O(n²).
What are the benefits and downsides of selection sort?
It is simple and can easily be implemented in linked lists.
However, it is inefficient for large input sets, as it runs at an order of O(n²).
What is the general process for a insertion sort algorithm?
A pointer x, at the end of the list, and y, directly before it, create a “partition” at the end. With each loop, our y pointer decreases by one, letting a new element into the partition.
We then check if this new element is sorted. If it is not, we move it slowly along the partition until it is.
Repeat this until the list is sorted.
What does it mean for an algorithm to be “in-place”?
An in-place algorithm is one that does not create a new object to store the sorted data.
What is the order of an insertion sort algorithm?
O(n²).
What is the primary use of an insertion sort algorithm?
Insertion sort is typically used when we want a solution that is not in-place - that is, a solution that creates a new list at the end.
Note that insertion sort can be done in-place, but is most commonly used for the above.
What is the general process for a bubble sort algorithm?
We go through the list backwards.
For each element in the list, if that element is greater than the element before it, swap them.
Keep looping until everything is sorted.
What is the order of a bubble sort algorithm?
O(n²).
What is meant by a “divide-and-conquer” algorithm?
A divide and conquer algorithm splits a problem into many smaller subtasks, and then combines their solution into a solution for the larger instance.
What is the general method of a Quicksort algorithm?
We pick one item from the list (e.g. list[i]), at any point, and call it the pivot. Commonly, we pick the middle element.
We then reorganise the list so that all smaller elements are placed before the pivot, and all larger elements are placed after the pivot.
We then call Quicksort again to solve the partitions. We can also use another sorting algorithm on these partitions if we want it to be simpler.
What is the master theorem for divide and conquer algorithms?
The master theorem is a theorem that is always correct for determining the order of a D&C algorithm.
It states that:
T(n) = O(nᵈ) if a < bᵈ
T(n) = O(nᵈ log n) if a = bᵈ
T(n) = O(nˡᵒᵍᵇ ᵃ) if a > bᵈ
Where a is the number of subproblems created at each stage…
b is the divisor of the size of the array…
and d is the number of subproblems created at each recursive stage.
What is the order of a Quicksort algorithm?
O(n log n).
What is the general method of a Mergesort algorithm?
We recursively break the given input array by half each time until the array cannot be split anymore.
When this is done, and we have many arrays consisting of one element, we recursively merge each “pair” of arrays by choosing the smallest element and putting it into the front of a new array.
When we have done this to every pair of arrays, we have a sorted list.
What is the order of a Mergesort algorithm?
O(n log n).
What are the benefits and downsides of using Mergesort?
It is stable, robust and performs in O(n log n), which is the best you can get in terms of speed in comparison-type sorting methods.
However, it may require an array of up to the size of the original list to use as an auxillary array. This is not necessary, however the algorithm becomes significantly more complex if we don’t use one.
What is the difference between Least Significant and Most Significant Digit RadixSort?
LSD (Least) starts from the first, or least significant, digit in the sequence.
What is the general method of a RadixSort algorithm?
We start by converting the keys we have been given into their bases. For example, we may want to strip an integer down to its digits.
When we sort using the LSD, we start at the rightmost digit and sort based on that digit. We then iteratively sort each digit sequence backwards until we have reached the final digit in the sequence.
When we sort using the MSD, we start at the leftmost digit and sort forwards. LSD is typically preferred as we have to sort less digits for our algorithm to be completed.
What is the order of a RadixSort algorithm?
Assuming the use of a form of Quicksort to sort each digit, O(n).
What is the benefit to using RadixSort?
RadixSort is not only the best method for multi-key sorting, as it can be performed on any set of data that can be represented bitwise, but it is also completely stable, making it perfect for large databases.
It’s also blazing fast - in best-case it can reach O(n) complexity, breaking the limit on comparison-based algorithms while also being totally stable.
What is the general method of a Counting Sort algorithm?
We first count the number of times a certain digit appears in the list, and store it in a seperate array, called a count array, that is as large as the range of numbers to be sorted.
Then, we compute a cumulative sum of the count array, to aid with placing elements back in the array.
Finally, we count backwards from the end of the original array, and when we find a number, we check its cumulative sum in the count array, and place it there. We also decrement the cumulative sum, so that duplicates are placed before it.
What do we need to know before starting a Counting Sort algorithm?
We need to know the range of numbers in the array, so that we can accurately create a count array.
What is the order of a Counting Sort algorithm?
O(k + n), where k is the range of values in the input array.
