Chapter 25 - Sorting Flashcards
Sorting is a classic subject in computer science. There are three reasons to study sorting algorithms. What are they?
First, sorting algorithms illustrate many creative approaches to problem solving, and these approaches can be applied to solve other problems.
Second, sorting algorithms are good for practicing fundamental programming techniques using selection statements, loops, methods, and arrays.
Third, sorting algorithms are excellent examples to demonstrate algorithm performance.
Where in the Java API can we find sorting methods?
in the java.util.Arrays and java.util.Collections classes.
How does the bubble sort work?
The bubble sort algorithm makes several passes through the array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise, the values remain unchanged. The technique is called bubble sort because the smaller values gradually “bubble” their way to the top.
What is the best-case time and the worst-case time for a bubble sort?
In the best-case analysis, the bubble sort algorithm needs just the first pass to find that the array is already sorted – no next pass is needed. Since the number of comparisons is n - 1 in the first pass, the best-case time for a bubble sort is O(n).
In the worst-case analysis, the bubble sort algorithm requires n - 1 passes. The first pass makes n - 1 comparisons; the second pass makes n - 2 comparisons; and so on; the last pass makes 1 comparison. Thus, the total number of comparisons is O(n^2).
How does the merge sort work?
The merge sort algorithm divides the array into two halves and applies a merge sort on each half recursively. The recursive call continues dividing the array into subarrays until each subarray contains only one element. The algorithm then merges these small subarrays into larger sorted subarrays until one sorted array results.
What is the time complexity of the merge sort algorithm?
The time complexity of a merge sort is O(n log(n))
This algorithm is better than selection sort, insertion sort, and bubble sort, because the time complexity of these algorithms is O(n^2).
How does the quick sort work?
Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
What is the time complexity of the quick sort algorithm?
The worst-case time is O(n^2). The average-case time is O(n log(n)).
What is a binary tree?
A binary tree is a hierarchical structure. It either is empty, or it consists of an element, called the root, and two distinct binary trees, called the left subtree and the right subtree.
The length of a path is the number of edges in the path, the depth of a node is the length of the path from the root to the node.
What is a binary heap?
A binary heap is a binary tree with the following properties:
- Shape property: It is a complete binary tree.
- Heap property: Each node is greater than or equal to any of its children.
A binary tree is complete if each of its levels is full, except that the last level may not be full if all the leaves on the last level are placed leftmost.
How do you store a binary heap? (data structure)
A heap can be stored in an ArrayList or an array if the heap size is known in advance. Consider the array:
[62, 42, 59, 32, 39, 44, 13, 22, 29, 14, 33]
For a node at position i, its left child is at position 2i + 1, its right child is at position 2i + 2, and its parent is (i - 1)/2. For example, the node for element 39 is at position 4, so its left child (element 14) is at 9 (24+1), its right child (element 33) is at 10 (24+2), and its parent (element 42) is at 1((4-1)/2) (rounded down).
What is the algorithm for adding a new node to a binary heap?
To add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:
let the last node be the current node;
while (current node > current node's parent) {
- swap current node with its parent;
- (current node is now one level up)
}
What is the algorithm for removing the root in a binary heap?
Often you need to remove the maximum element, which is the root in a heap. After the root is removed, the tree must be rebuilt to maintain the heap property. The algorithm for rebuilding the tree can be described as follows:
move last node to replace root;
let the root be the current node;
while (current node has children and
- current node is smaller than one of them) {
- swap current node with largest of its children;
- (now current node is one level down)
}
What is the time complexity of a heap sort?
The worst-case time of heap sort is O(n log(n)).
Both merge sorts and heap sorts require O(n log(n)) time. A merge sort requires a temporary array for merging two subarrays; a heap sort does not need additional array space. Therefore, a heap sort is more space efficient than a merge sort.
What is bucket sort, and how does it work? What is its time complexity?
The lower bound for general sorting algorithms is O(n log(n)), so no sorting algorithms based on comparisons can perform better than O(n log(n)). However, if the keys are small integers, you can use bucket sort without having to compare the keys.
The bucket sort works as follows. Assume the keys are in the range from 0 to t. We need t + 1 buckets labeled 0, 1, …, and t. If an element’s key is i, the element is put into the bucket i. Each bucket holds the elements with the same key value. You can use a nested ArrayList to implement a bucket.
It takes O(n + t) time to sort the list and uses O(n +1) space, where n is the list size. Note that if t is too large, using the bucket sort is not desirable. Instead, use radix sort.
