Chapter 11 Flashcards
What Q(n) time algorithm do
Normally, a Q (n) time algorithm would make a single or perhaps a constant number of passes of the data set.
Array of objects sort on which attribute
the key value
What are slow O(n2) sorting algorithms
Bubble sort, Insertion sort, Selection sort
What is bubble sort
Scan the array. Whenever two consecutive items are found that are out of order, swap them. Repeat until all consecutive items are in order.
What is insertion sort
Assume that A[1..i - 1] have already been sorted. Insert A [i] into its proper position in this sub array. Create this position by shifting all larger elements to the right.
What is Selection sort
The selection sort is a combination of searching and sorting. During each pass, the unsorted element with the smallest (or largest) value is moved to its proper position in the array. The number of times the sort passes through the array is one less than the number of items in the array.
What is the worst case of running of Bubble sort, Insertion sort, Selection sort
Q(n2)
What are 3 methods of sorting in O(n log n) time
Merge sort
Heap sort
Quick sort
What is heap
A heap is a left-complete binary tree that confirms to the heap order. The parent node has key smaller than or equal to both of its children nodes.
What is max heap
in a max heap, the parent has a key larger than or equal both of its children Thus the smallest key is in the root in a min heap; in the max heap, the largest is in the root.
Does heap use pointer
No
Which order traversal is used in heap tree
level-order traversal
What arithmetic operation is required to access left node in heap tree
returns 2i
What arithmetic operation is required to access right node in heap tree
returns 2i + 1
What arithmetic operation is required to access parent node in heap tree
returns bi/2c
