Sorting Flashcards
What is the worst case and best case of selection sort?
Worst when array reverse sorted: N^2 /2 comparisons and N swaps
Best when array already sorted:
N^2/2 comparisons and 0 swaps.
What is the best and worst case of insertion sort?
Worst: reverse order arrayN^2 / 4 compares, N^2/2 exchanges
Best: Sorted array N - 1 compares and 0 exchanges
What is the best and worst case of mergesort?
Between 0.5N log N and N log N compares
at most 6N lg N array acccesses
How efficient is merge sort at random/sorted/reverse sorted/identical array?
Always has complexity of N log N
Why use random shuffling in quick sort and what are the issues with distinct keys?
Random shuffling is employed in QuickSort to prevent worst-case time complexity scenarios, particularly when the input array is already sorted or nearly sorted.
When input arrays contain duplicates, the partitioning process selects pivot elements that are the same as the majority of elements in the array. This makes partitioning highly unbalanced.
Poorly chosen pivots that do not divide array into equal halves, leading to unbalanced partitions. This leads to a higher probability of worst-case scenarios.
For example, if the pivot is always chosen as the first or last element and it is already sorted, Quick Sort will end up with unbalanced partitions leading to a time complexity of $N^2$.
How does one maintain the heap order of a binary tree?
The insert and delete operations must be able to move
a large element up the tree (swim) or move small elements to the bottom (sink), in order to maintain heap
order.
How does the data type/object to be sorted, influence the efficiency of the sorting algorithm?
- Comparison overhead: Efficiency of comparisons vary based on the complexity of operation for the data type.
- Data distribution: [[Quick Sort]] performs poorly on sorted data but excels on average or random
- Data Size
- Stability
- Memory requirements: [[Mergesort]] requires additional storage
why a heap-ordered binary tree has height ~lg N in all cases (why can it not have height N, like a normal binary tree that is created using sorted data?)
- Balanced Structure
- Complete Binary Tree Property: Amount of nodes are doubled after each parent.
- Heap Property: Number of comparisons needed to reach maximum node is logarithmic to the number of elements in the heap.
When should quick sort be used?
Large sets where average-case performance is acceptable and when data is not sorted.
When should merge sort be used?
Sorting large lists. Merge sort executes operational steps even if the initial list is already sorted.
What is heap sort’s time complexity?
Always $N \log N$.
What is the worst case for Heap Sort?
2N lg N + 2N
When is an array partially sorted?
If the number of in-versions < constant multiple of size.
How is a binary heap implemented using an array?
- Indexing using (2k, 2k+1, k/2) formulas
- Insertion added to end of array
- Deletion where maximum element is removed and replaced with last element. Compare new root with children.
What is the average case for quick sort?
2N ln N compares and 1/3 N ln N exchanges
