Week 11- Sorting Flashcards
What is the Divide and Conquer (D&C) paradigm in algorithm design?
Divide and Conquer (D&C) is an algorithm design paradigm that recursively breaks a problem down into smaller, more manageable sub-problems of the same type, solves each sub-problem, and then combines the results.
What is the precondition for applying the Divide and Conquer approach effectively?
The precondition is often that the data is sorted. This helps the algorithm break down problems more efficiently and combine solutions, as seen in algorithms like Merge Sort or Binary Search.
How does the Divide and Conquer strategy work?
Divide: Split the original problem into smaller sub-problems.
Conquer: Solve each sub-problem recursively.
Combine: Merge the solutions of the sub-problems to form the solution to the original problem.
Why is Divide and Conquer effective for sorted data?
Divide and Conquer works efficiently on sorted data because it allows algorithms to split the problem space (such as searching or sorting) in a way that minimizes unnecessary work, leveraging the sorted order to reduce complexity (e.g., Binary Search or Merge Sort).
What is Quicksort?
Quicksort is a Divide and Conquer algorithm developed by Tony Hoare in 1961. It efficiently sorts an array by recursively partitioning it into smaller sub-arrays.
What is the first step of the Quicksort algorithm?
Select an element from the array, called the Pivot. The pivot is used to partition the array into smaller sub-arrays.
What happens in Step 2 of the Quicksort algorithm?
Partition the array by moving all elements smaller than the Pivot to the left of the Pivot, and all elements greater than the Pivot to the right. This creates two sub-arrays.
What is the final step of the Quicksort algorithm?
Apply Step 1 and Step 2 recursively to each sub-array (left and right) until the entire array is sorted.
What is Heapsort?
Heapsort is a comparison-based sorting algorithm developed by John William Joseph Williams in 1964. It sorts an array by using a binary heap data structure, specifically a Max Heap or Min Heap.
What are the key concepts required to understand Heapsort?
The key concepts required for Heapsort include:
- Priority Queue
- Complete Balanced Tree
- Heap
- Heapify
- Build a Max Heap
What is a Priority Queue (PQ)?
A Priority Queue (PQ) is an abstract data type where each element has a priority associated with it. Elements are processed based on their priority rather than their insertion order.
How is the priority of an element in a Priority Queue (PQ) determined?
The priority is determined by the value of the element. For example, in a Max Priority Queue, the largest value has the highest priority, while in a Min Priority Queue, the smallest value has the highest priority.
What are the three key operations that a Priority Queue (PQ) must support?
A Priority Queue (PQ) must support at least three operations:
is_empty: Check if the queue is empty.
insert: Add an element with an associated priority.
pull: Remove and return the element with the highest priority from the queue.
What does the is_empty operation do in a Priority Queue (PQ)?
The is_empty operation checks whether the Priority Queue (PQ) is empty and returns true if no elements are in the queue, or false if there are elements.
What does the insert operation do in a Priority Queue (PQ)?
The insert operation adds an element to the Priority Queue (PQ) and assigns it a priority. The queue maintains the priority order based on the element’s value.
What does the pull operation do in a Priority Queue (PQ)?
The pull operation removes and returns the element with the highest priority in the Priority Queue (PQ), which is either the largest or smallest element depending on the type of priority queue (Max or Min).
What is a Complete Binary Tree?
A Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
What are the key properties of a Complete Binary Tree?
The key properties of a Complete Binary Tree are:
All levels, except possibly the last, are completely filled.
Nodes at the last level are filled from left to right, without any gaps.
How does a Complete Binary Tree differ from a regular binary tree?
In a Complete Binary Tree, every level must be filled from left to right, while in a regular binary tree, there can be any arrangement of nodes at any level, including gaps.
What is the significance of a Complete Binary Tree in data structures like heaps?
Complete Binary Trees are used in heaps because their structure ensures efficient operations (like insertion and removal of the root) with a predictable tree shape, ensuring O(log n) time complexity for key operations.
What is a Binary Heap?
A Binary Heap is a Complete Binary Tree that satisfies the heap property (also called heap invariant). It is used to efficiently implement priority queues.
What is the heap property in a Binary Heap?
The heap property states that the key/value stored in each node is either:
Greater than or equal to (>=) the keys/values in its children (Max-Heap).
Less than or equal to (<=) the keys/values in its children (Min-Heap).
