2.3.3 Sorting Algorithms

• What is the purpose of sorting algorithms?

  To arrange elements in logical order
• What types of order do sorting algorithms typically output?

  Numerical or lexicographic order
• How can sorting algorithms be modified to output in descending order?

  By switching an inequality or reversing output
• What is the basic operation of bubble sort?

  Comparisons and swaps between pairs
• What happens to the largest element during bubble sort?

  It "bubbles" to the top of the data
• What does one pass of bubble sort accomplish?

  Places the largest element in the last position
• How many passes does bubble sort perform for an array with n elements?

  n passes
• What is the pseudocode structure for bubble sort?

  Two nested loops comparing adjacent elements
• What is the purpose of the temporary store in bubble sort?

  To facilitate the swap operation
• What indicates the end of the first pass in bubble sort?

  The largest element is in the last position
• What modification improves the bubble sort algorithm?

  Introducing a flag to track swaps
• What does the noSwap flag indicate in the improved bubble sort?

  No swaps occurred during a full pass
• What is the time complexity of bubble sort?

  O(n²)
• How does insertion sort differ from bubble sort?

  It places elements into a sorted sequence
• What does the ith iteration of insertion sort accomplish?

  Sorts the first i elements of the array
• How does insertion sort insert an element into the sorted sequence?

  By moving larger elements to the right
• What is the time complexity of insertion sort?

  O(n²)
• What is the main concept behind merge sort?

  Divide and conquer strategy
• What are the two functions involved in merge sort?

  MergeSort and Merge
• What does MergeSort do with its input?

  Divides it into two parts recursively
• What is the worst-case time complexity of merge sort?

  O(n log n)
• How does the merging process work in merge sort?

  Compares and combines elements from lists
• What is the role of the pivot in quick sort?

  To divide the input around it
• What is the time complexity of quick sort?

  O(n²)
• How does quick sort determine the position of the pivot?

  By selecting the central element
• What happens to old pivots in quick sort?

  They remain in their correct position
• What is the stopping condition for quick sort?

  All elements are old pivots or length 1