• Bubble Sort is a sorting algorithm that works by repeatedly iterating through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. This is repeated until no swaps are needed, which indicates that the list is sorted. Write down the Bubble Sort algorithm in pseudocode including comments to explain the steps and/or actions.
  • Determine and prove the asymptotic worst-case, average-case, and best-case time complexity of Bubble Sort.
  • Stable sorting algorithms maintain the relative order of records with equal keys (i.e., values). Thus, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. Which of the sorting algorithms Insertion Sort, Merge Sort, Heap Sort, and Bubble Sort are stable? Explain your answers.
  • ( A sorting algorithm is adaptive, if it takes advantage of existing order in its input. Thus, it benefits from the pre-sortedness in the input sequence and sorts faster. Which of the sorting algorithms Insertion Sort, Merge Sort, Heap Sort, and Bubble Sort are adaptive? Explain your answers.

Problem 6.2 Heap Sort

• Implement the Heap Sort algorithm as presented in the lecture.
• (Implement a variant of the Heap Sort that works as follows: In the first step it also builds a max-heap. In the second step, it also proceeds as the Heap Sort does, but instead of calling MAXHEAPIFY , it always floats the new root all the way down to a leaf level. Then, it checks whether that was actually correct and if not fixes the max-heap by moving the element up again. This strategy makes sense when considering that the element that was swapped to become the new root is typically small and thus would float down to a leaf level in most cases. Hence, one would save the additional tests when floating down the element. And, the fixing step (moving the element upwards again) would be a rare case.
• Bonus Compare the original HeapSort and its variant from subpoint (b) for input sequences of different lengths (including larger input sequences). What can you observe?