MOD 8_ZYBOOKS 10_SORTING Flashcards
(17 cards)
What is sorting?
What is the challenge of sorting?
What is selection sort?
Selection sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
Explain how selection sort works.
The index variable i denotes the dividing point. Elements to the left of i are sorted, and elements including and to the right of i are unsorted. All elements in the unsorted part are searched to find the index of the element with the smallest value. The variable indexSmallest stores the index of the smallest element in the unsorted part. Once the element with the smallest value is found, that element is swapped with the element at location i. Then, the index i is advanced one place to the right, and the process repeats.
The term “selection” comes from the fact that for each iteration of the outer loop, a value is selected for position i.
Selection sort has the advantage of being easy to code, involving one __(same)__ nested within another __(same)__.
Loop
VIEW: Selection sort algorithm
What is insertion sort?
Insertion sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.
Explain how insertion sort works.
The index variable i denotes the starting position of the current element in the unsorted part. Initially, the first element (i.e., element at index 0) is assumed to be sorted, so the outer for loop initializes i to 1. The inner while loop inserts the current element into the sorted part by repeatedly swapping the current element with the elements in the sorted part that are larger. Once a smaller or equal element is found in the sorted part, the current element has been inserted in the correct location and the while loop terminates.
VIEW: Insertion sort algorithm
What is a nearly sorted list?
For sorted or nearly sorted inputs, insertion sort’s runtime is O(N). A nearly sorted list only contains a few elements not in sorted order. Ex: (4, 5, 17, 25, 89, 14) is nearly sorted having only one element not in sorted position.
What is a max-heap?
Which node always has the maximum key in the entire tree?
How does a max-heap insert operation work?
What does percolating mean?
An insert into a max-heap starts by inserting the node in the tree’s last level, and then swapping the node with its parent until no max-heap property violation occurs. Inserts fill a level (left-to-right) before adding another level, so the tree’s height is always the minimum possible. The upward movement of a node in a max-heap is called percolating.
How does a max-heap remove operation work?
A remove from a max-heap is always a removal of the root, and is done by replacing the root with the last level’s last node, and swapping that node with its greatest child until no max-heap property violation occurs. Because upon completion that node will occupy another node’s location (which was swapped upwards), the tree height remains the minimum possible.
What is a min-heap?
A min-heap is similar to a max-heap, but a node’s key is less than or equal to its children’s keys.
Describe how heap storage works and how its array form is traversed.
Heaps are typically stored using arrays. Given a tree representation of a heap, the heap’s array form is produced by traversing the tree’s levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root’s left child is the entry at index 1, the root’s right child is the entry at index 2, and so on.
VIEW: Parent and child indices for a heap
Because heaps are not implemented with node structures and parent/child pointers, traversing from a node to parent or child nodes requires referring to nodes by index. The table below shows parent and child index formulas for a heap.
VIEW: Max-heap percolate up algorithm
Following is the pseudocode for the array-based percolate-up and percolate-down functions. The functions operate on an array that represents a max-heap and refer to nodes by array index.
VIEW: Max-heap percolate down algorithm
