Bubble Sort for an Array: Performance Analysis
• In worst case, outer loop runs __ times
• In worst case, the inner loop depends on the outer loop.
• Hence, it is on the order of ___
• In best case, no more swapping is needed since the order is already sorted, so the ____ loop is not executed (except once)
• In that case, the algorithm is on the order ___
• Drawbacks
• __________ bubbles up to sorted position in every loop
• Swapping can be _________________ عارف مش عارف .
Insertion Sort for an Array: Performance
Analysis
• In worst case, Inner loop runs ________ times
• The array is in exactly ______________
• Efficiency is ________
• In the best case, the array is already sorted, hence the inner loop ________
• In that case, the efficiency is ___
• Simple and efficient for ________
• Drawbacks:
• Places ___ in sorted position at a time عارف مش عارف.
Selection Sort for an Array: Performance Analysis
• In worst case, outer loop runs __ times
• In worst case, the inner loop depends ________________
• Hence, it is on the order of ____
• In best case, _______________________
• In that case, the algorithm is _______
• _______ than insertion sort in the best case not efficient عارفه مش عارفه .
Linear Search (Sorted/Unsorted Arrays):
• Performance analysis
• Also very simple: O(n) in worst case
• Average case: record found in _________
• Regardless of whether array or linked list
• Regardless of whether sorted or unsorted عارف مش عارف .
Binary Search (Sorted Array):
Performance Analysis
• Loop constantly splits the array into smaller halves
• There are at most log2(n) subarrays that are generated
• For each subarray, there are at most 3 comparisons
• Therefore O(log2(n))
• Much faster than linear search of sorted arrays عارف مش عارف.
BST Operations: Performance Analysis
• For a balanced tree:
• search: ______
• insert: ______
• delete: ______
• For the most unbalanced tree (one branch has all the data):
• search: ______
• insert: ______
• delete: ______ عارف مش عارف .
|
