Basic Sorts
Definition of Sorting
An ordering relation < for keys a, b, and c has the following properties:
Law of Trichotomy: Exactly one of a < b, a = b, b < a is true.
Law of Transitivity: If a < b, and b < c, then a < c.
A sort is a permutation (re-arrangement) of a sequence of elements that puts the keys into non-decreasing order relative to a given ordering relation. In Java, ordering relations are typically given in the form of compareTo or compare methods.
import java.util.Comparator;
public class LengthComparator implements Comparator<String> {
public int compare(String x, String b) {
return x.length() - b.length();
}
}Performance of Algorithms
The Time Complexity of an algorithm is the characterization of its runtime efficiency. Dijkstra’s has time complexity O(E log V).
The Space Complexity of an algorithm is the characterization of its extra memory usage. Dijkstra’s has space complexity Θ(V).
Selection Sort
Steps of Selection Sort
Find the smallest item.
Swap the item to the front and fix it.
Repeat for unfixed items until all items are fixed.
Runtime
Θ(N^2) time if an array is used to store the items.
Heap Sort
Naive
Maintain a max-oriented heap to get the maximum item fast.
Insert all items into a max heap, and discard input array. Create output array.
Delete largest item from the max heap.
Put largest item at the end of the unused part of the output array.
Runtime
Getting items into the heap
O(N log N)time.Selecting largest item:
Θ(1)time.Removing largest item:
O(log N)for each removal.The overall runtime is
O(N log N).
In-Place
Rather than inserting into a new array of length N + 1, use a process known as “bottom-up heapification” to convert the array into a heap. This approach could avoid the need for extra copy of all data.
Runtime
The Time Complexity of In-Place Heap Sort is the same as the Naive Heap Sort.
The Space Complexity of In-Place Heap Sort is
Θ(1).
Merge Sort
Split items into 2 roughly even pieces.
Mergesort each half recursively.
Merge the two sorted halves to form the final result.
Runtime
The Time Complexity of Merge Sort is
Θ(N log N).The Space Complexity of Merge Sort is
Θ(N).
Insertion Sort
Starting with an empty output sequence.
Add each item from input, inserting into output at right point.
Perform these steps in place by swapping with previous items.
Example:
P O T A T O (0 swap)
O P T A T O (1 swap)
O P T A T O (0 swap)
A O P T T O (3 swaps)
A O P T T O (0 swap)
A O O P T T (3 swaps)On arrays with a small number of inversions, insertion sort is extremely fast. For small arrays (N < 15 or so), insertion sort is fastest.
Runtime
The best case for insertion sort is
Θ(N).The worst case of insertion sort is
Θ(N ^ 2).
Last updated