3.1.4 Sorting algorithms

• What is the primary purpose of sorting algorithms?

  Arrange elements in order
• Stability in a sorting algorithm refers to maintaining the relative order of equal elements
• Comparison-based sorting algorithms typically have a time complexity of O(n^2).

  True
• Selection Sort finds the minimum element from the unsorted part of the array and swaps it with the first element of the unsorted part.


  True
• The time complexity of comparison-based sorting algorithms is typically O(n^2).
• Bubble Sort is a stable sorting algorithm.
• What are sorting algorithms used for?

  Arranging elements in order
• Common examples of comparison-based sorting algorithms include Bubble Sort, Insertion Sort, and Selection Sort.
• Comparison-based sorting algorithms sort elements by repeatedly comparing and swapping them.


  True
• In comparison-based sorting algorithms, elements are swapped if they are in the wrong order
• How does Bubble Sort indicate that the list is sorted?

  No swaps are needed
• What are the time complexity and stability of Bubble Sort?

  O(n^2), stable
• What are the time complexity and stability of Insertion Sort?

  O(n^2), stable
• Selection Sort is not stable because it may change the relative order of equal elements
• What are the time complexity and stability of Selection Sort?

  O(n^2), not stable
• Steps in sorting the list `[5, 1, 4, 2, 8]` using Selection Sort

  1️⃣ Find minimum element (1) and swap with 5: `[1, 5, 4, 2, 8]`

  2️⃣ Find minimum element (2) and swap with 5: `[1, 2, 4, 5, 8]`

  3️⃣ Find minimum element (4), no swap needed: `[1, 2, 4, 5, 8]`

  4️⃣ Find minimum element (5), no swap needed: `[1, 2, 4, 5, 8]`
• Selection Sort is not a stable sorting algorithm
• The efficiency of a sorting algorithm is measured by its time and space complexity
• Steps in the general approach of comparison-based sorting algorithms

  1️⃣ Compare two elements

  2️⃣ Swap them if they are in the wrong order

  3️⃣ Repeat until the entire list is sorted
• Bubble Sort compares and swaps adjacent elements to sort a list.


  True
• Bubble Sort stops when no swaps are needed in a pass
• Bubble Sort repeatedly steps through the list until no swaps are needed
• Is Bubble Sort a stable sorting algorithm?

  Yes
• Insertion Sort is efficient for large, unsorted lists.

  False
• How does Selection Sort work?

  Find minimum and swap
• Selection Sort is a stable sorting algorithm.

  False
• Match the sorting algorithm with its properties:

  Selection Sort ↔️ Not stable, O(n^2)

  Bubble Sort ↔️ Stable, O(n^2)

  Merge Sort ↔️ Stable, O(n log n)
• Non-comparison-based sorting algorithms often result in faster performance for specific data types
• For which data type is Counting Sort most efficient?

  Integers
• Non-comparison-based sorts are data-type specific.

  True
• Non-comparison sorts are more versatile than comparison-based sorts.

  False
• Counting Sort has a time complexity of O(n + k)
• Steps of the Counting Sort algorithm:

  1️⃣ Count the occurrences of each element in the input array

  2️⃣ Build a cumulative frequency array from the count array

  3️⃣ Use the cumulative frequency array to place each element in its correct position in the output array
• The time complexity of a sorting algorithm measures how long it takes to sort a list of n elements.


  True
• Sorting algorithms are used for data analysis and database management.

  True
• Comparison-based sorting algorithms always have a time complexity of O(n^2).

  False
• Bubble Sort repeats passes through the list until no swaps
• The pass through the list in Bubble Sort is repeated until no swaps are needed
• Steps in the first pass of Bubble Sort with the list [5, 1, 4, 2, 8]

  1️⃣ Compare 5 and 1, swap: [1, 5, 4, 2, 8]

  2️⃣ Compare 5 and 4, swap: [1, 4, 5, 2, 8]

  3️⃣ Compare 5 and 2, swap: [1, 4, 2, 5, 8]

  4️⃣ Compare 5 and 8, no swap: [1, 4, 2, 5, 8]
• In the second pass of Bubble Sort with the list [1, 4, 2, 5, 8], 1 and 4 are compared but not swapped