KC 28: Sorting

1. What is the primary goal of a sorting algorithm?

• To find the largest element in a list.
• To arrange elements in a specific order (e.g., ascending or descending).
• To remove duplicate elements from a list.
• To count how many elements are in a list.

2. Which Computational Thinking concept is most directly related to designing the steps of a sorting algorithm like Bubble Sort or Selection Sort?

• Abstraction (Hiding complex details).
• Decomposition (Breaking down a problem).
• Pattern Recognition (Finding similarities).
• Algorithm Design (Creating step-by-step instructions).

3. What is the core operation performed repeatedly in Bubble Sort?

• Finding the smallest element in the unsorted portion.
• Comparing adjacent elements and swapping them if they are in the wrong order.
• Dividing the list into smaller sub-lists.
• Inserting an element into its correct position in a sorted portion.

4. Consider the list [5, 1, 4, 2]. After the *first pass* of Bubble Sort (comparing and swapping adjacent elements from left to right), what will the list look like?

• [1, 5, 4, 2]
• [1, 4, 2, 5]
• [5, 1, 2, 4]
• [1, 5, 2, 4]

5. What is the core operation performed in each pass of Selection Sort?

• Swapping every adjacent pair that is out of order.
• Finding the minimum (or maximum) element in the unsorted portion and swapping it to the beginning of the unsorted portion.
• Merging two sorted halves of the list.
• Picking an element and comparing it to all others.

6. Consider the list [5, 1, 4, 2]. After the *first pass* of Selection Sort (finding the minimum and swapping it with the first element), what will the list look like?

• [1, 5, 4, 2]
• [5, 1, 2, 4]
• [1, 4, 5, 2]
• [1, 2, 4, 5]

7. How many swaps does Selection Sort perform in the worst case for a list of N elements?

• Exactly N swaps.
• At most N-1 swaps.
• It depends on the initial order, could be many more than N swaps (like Bubble Sort).
• Zero swaps if the list is already sorted.

8. Which simple sorting algorithm might finish early if the list becomes sorted during one of its passes?

• Selection Sort
• Bubble Sort (if implemented with an optimization flag)
• Both Bubble Sort and Selection Sort
• Neither, they always complete all passes.

9. In general, for large, randomly ordered lists, are Bubble Sort and Selection Sort considered highly efficient compared to more advanced algorithms?

• Yes, they are the fastest simple sorts.
• No, they are generally slower than algorithms like Merge Sort or Quick Sort for large lists.
• They are efficient only if the list is almost sorted already.
• Their efficiency is comparable to advanced algorithms.

10. Why is understanding simple sorting algorithms like Bubble Sort and Selection Sort useful, even if more efficient ones exist?

• They are the only algorithms used in modern software.
• They help build foundational understanding of algorithmic concepts like comparison, swapping, and iteration.
• They are required for advanced AI development.
• They are primarily used for sorting text data.