2.1 Sorting and Searching

• What is an algorithm?

  Well-defined procedure
• The finiteness characteristic of an algorithm means it must eventually stop
• What does the definiteness characteristic of an algorithm ensure?

  Precisely defined steps
• An algorithm must always produce an output.
• Match the characteristic of an algorithm with its description:

  Finiteness ↔️ Eventually stops

  Definiteness ↔️ Precisely defined steps

  Input ↔️ Receives data

  Output ↔️ Produces a result
• What is an example of an input for a cake recipe as an algorithm?

  Ingredients
• Sorting algorithms are used for organizing data
• What does the Bubble Sort algorithm do?

  Compares and swaps adjacent elements
• The Selection Sort algorithm finds the smallest element and moves it to the front
• How does the Insertion Sort algorithm build a sorted sequence?

  By inserting elements one by one
• Merge Sort has a worst-case complexity of O(n log n).
• Quick Sort chooses a pivot and partitions the array around it.
• What does Bubble Sort repeatedly compare and swap?

  Adjacent elements
• Selection Sort finds the smallest element and moves it to the front
• How does Insertion Sort build a sorted sequence?

  Inserting elements one by one
• Quick Sort partitions around a pivot element.
• Steps of Merge Sort algorithm

  1️⃣ Divide array into halves

  2️⃣ Recursively sort each half

  3️⃣ Merge the sorted halves
• What is the average-case time complexity of Quick Sort?

  O(n log n)
• In Quick Sort, the pivot is used to partition the array.
• What is the best-case time complexity of Bubble Sort?

  O(n)
• What is the worst-case time complexity of Selection Sort?

  O(n^2)
• Insertion Sort has a worst-case time complexity of O(n^2).
• Match the sorting algorithm with its pseudocode:

  Bubble Sort ↔️ `FOR i FROM 0 TO n-2: FOR j FROM 0 TO n-i-2: IF array[j] > array[j+1]: SWAP array[j] and array[j+1]`

  Selection Sort ↔️ `FOR i FROM 0 TO n-1: minIndex = i: FOR j FROM i+1 TO n-1: IF array[j] < array[minIndex]: minIndex = j: SWAP array[i] and array[minIndex]`

  Insertion Sort ↔️ `FOR i FROM 1 TO n-1: key = array[i]: j = i-1: WHILE j >= 0 AND array[j] > key: array[j+1] = array[j]: j = j-1: array[j+1] = key`

  Merge Sort ↔️ `MERGE_SORT(array, start, end): IF start < end: mid = (start+end)/2: MERGE_SORT(array, start, mid): MERGE_SORT(array, mid+1, end): MERGE(array, start, mid, end)`

  Quick Sort ↔️ `QUICK_SORT(array, start, end): IF start < end: pivotIndex = PARTITION(array, start, end): QUICK_SORT(array, start, pivotIndex-1): QUICK_SORT(array, pivotIndex+1, end)`
• What is the worst-case time complexity of Merge Sort?

  O(n log n)
• Quick Sort has a worst-case time complexity of O(n^2).
• The efficiency of sorting algorithms is primarily determined by their time complexity.
• Which sorting algorithm has a best-case time complexity of O(n^2)?

  Selection Sort
• What is the worst-case time complexity of Merge Sort?

  O(n log n)
• Quick Sort has a worst-case time complexity of O(n log n).

  False
• What is the best-case time complexity of Bubble Sort?

  O(n)
• Which sorting algorithm has a worst-case time complexity of O(n^2)?

  Selection Sort
• The best-case time complexity of Bubble Sort is O(n).
• Which sorting algorithm has a best-case time complexity of O(n log n)?

  Merge Sort
• Bubble Sort has a best-case time complexity of O(n^2).

  False
• What is the worst-case time complexity of Quick Sort?

  O(n^2)
• Merge Sort and Quick Sort perform better on large datasets due to their average-case complexity of O(n log n).
• What are the key characteristics of an algorithm?

  Finiteness, definiteness, input, output
• An algorithm must eventually stop.
• Match the algorithm characteristic with its description:

  Finiteness ↔️ The algorithm must stop.

  Definiteness ↔️ Each step must be precise.

  Input ↔️ The algorithm receives data.

  Output ↔️ The algorithm produces a result.
• An algorithm must eventually stop.