Sorting

Topics in this chapter

• Python Sorting Tools
• Selection Sort Logic
• Insertion Sort Logic
• Bubble Sort Logic
• Sorting Analysis And Correctness

Cheat sheet

Practice questions

1. Question 1Q-2625C0

   Which statement correctly describes the difference between list.sort() and sorted() in Python?

   1. A.list.sort() returns a new sorted list, while sorted() changes the original list.
   2. B.list.sort() changes the original list, while sorted() returns a new sorted list.
   3. C.Both list.sort() and sorted() always change the original list.
   4. D.Neither list.sort() nor sorted() can arrange a list in descending order.
   See the answer and solution
2. Question 2Q-BE9757

   A single left-to-right pass of bubble sort is performed in ascending order on the list [7, 2, 5, 3, 1]. What will the list be after this pass?

   1. A.[1, 2, 3, 5, 7]
   2. B.[2, 5, 3, 1, 7]
   3. C.[2, 3, 5, 1, 7]
   4. D.[7, 2, 5, 3, 1]
   See the answer and solution
3. Question 3Q-445B2A

   For an already sorted list of n elements, explain why insertion sort can be more efficient than selection sort, and state the best-case time complexity of each algorithm.

   See the answer and solution
4. Question 4Q-91B611

   In an ascending selection sort, what will the list [64, 25, 12, 22, 11] become after the first pass?

   1. A.[11, 25, 12, 22, 64]
   2. B.[25, 64, 12, 22, 11]
   3. C.[12, 25, 64, 22, 11]
   4. D.[64, 25, 12, 11, 22]
   See the answer and solution
5. Question 5Q-188242

   Which combination correctly describes the standard in-place selection sort for a list of n elements?

   1. A.It performs Θ(n) comparisons and uses Θ(n) extra space.
   2. B.It performs Θ(n²) comparisons and uses O(1) auxiliary space.
   3. C.It performs Θ(n log n) comparisons and uses O(log n) auxiliary space.
   4. D.It performs Θ(n²) comparisons and uses Θ(n) auxiliary space.
   See the answer and solution