Sorting Algorithms Flashcards
What is the idea behind Insertion Sort
- Iteratively build a sorted portion of the array.
- Insert the next unsorted element into its proper place in the already sorted part.
- Insertion sort is in-place (requires no extra array).
What is the idea behind Selection Sort
- Repeatedly find the minimum element from the unsorted portion and place it at the beginning.
- Selection sort is in place
What is the idea behind Quick Sort
- Divide-and-conquer algorithm.
- Select a pivot element and partition the array into elements less than and greater than the pivot.
- Recursively sort the sub-arrays.
- Can be implemented in-place but is not stable
What is the idea behind Merge Sort
- Divide and conquer algorithm
- Divide the array into two halves, recursively sort each half, and then merge the sorted halves
- The standard merge sort is not in-place (requires O(n) extra space) but is stable
- In-place versions exist.
What is the idea behind Tree Sort
- Insert all elements into a balanced binary search tree (e.g. an AVL tree).
- Perform an in-order traversal to get the sorted sequence.
- Tree sort is not in-place.
- It can be stable if insertion preserves the order of equal elements.
What is the idea behind Heap Sort?
- Convert the array into a heap
- Repeatedly extract the largest element and place it at the end of the array.
- Heap sort is in-place but not stable
What is the concept of a divide-and-conquer sort?
Divide a problem into smaller sub-problems, solve them recursively and combine (conquer) the solutions
What are examples of a divide and conquer sort?
- merge sort (most of the work in the combining step)
- quick sort (most of the work in the dividing step)
What are examples of classic sorting algorithms?
- insertion sort (efficient for nearly sorted arrays)
- selection sort (consistently O(n²) regardless of input order)
What are examples of tree-based sorts
- tree sort (balanced binary search tree)
- heap sort (heap data structure)
What is the idea behind Bucket Sort?
Distribute elements into “buckets” based on their keys, then concatenate the buckets in order
What are is the Bucket Sort process?
For a sequence S of n items with integer keys in [0, d-1]:
- Create an array B of d empty buckets.
- For each item x in S: Determine its key k and remove x from S and append it to bucket B[k].
- After all items are distributed, S becomes empty.
- concatenate all items from bucket B[0] up to B[d-1] back into S in order.
What is an advantage of bucket sort
Efficient when the range d is small compared to n (e.g., 8- or 16-bit integers).
What are the limitations of bucket sort?
- Not feasible for sorting large-key ranges (e.g., 32-bit integers) due to high space use (O(d)).
- Not suitable for floating-point numbers (infinitely many possible values) or character strings (requires a unique bucket per key).
What is the idea behind Radix sort?
- Sort keys by processing individual digits (or characters) instead of using one overall key.
- Divides each key into digits; the number of possible digit values is called the radix (R).
What are the two types of Radix Sort?
- Most Significant Digit First (MSD)
- Least Significant Digit First (LSD)
What is the approach of MSD Radix Sort?
- Start by partitioning keys based on their most significant digit.
- Recursively sort each partition by the next most significant digit.
- Use R empty lists (buckets) for each digit value.
- For small lists, a simpler sort (like insertion sort) may be used.
- Finally, concatenate the sorted lists.
What is the approach of LSD Radix Sort?
- Process the keys by performing a series of stable bucket sorts on each digit, starting from the least significant digit and moving to the most significant.
- For each digit position:
Use R temporary lists. Place keys into lists based on the current digit. Concatenate the lists back into the input array.
Between MSD and LSD, which is stable?
LSD is stable, maintaining the relative order of equal keys. MSD is not stable since its relative order of equal keys may change.
