## Description

## Problem 1: Bubble Sort & Stable and Adaptive Sorting.s (3+2+3+2=10 points)

(a) Bubble Sort is a comparison sorting algorithm that works by repeatedly stepping 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 the Bubble Sort

algorithm in pseudocode including comments to explain the steps.

(b) Derive the asymptotic worst-case, average-case, and best-case running time of Bubble Sort.

(c) 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, Heapsort, and Bubble Sort are stable? Explain your answer.

(d) 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, Heapsort, and Bubble Sort are adaptive? Explain your answer.

## Problem 2: Heap Sort (8+4+3=15 points)

(a) Implement the Heap Sort algorithm as presented in class.

(b) 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 MAX-HEAPIFY, 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.

(c) Compare the original Heap Sort and its variant in (b) for input sequences of different lengths (including

larger input sequences). What can you observe?

## Remarks

Solutions have to be handed in via Moodle by the due date. For late submissions you need to get in contact

with the TAs directly. You need to upload one zip-file that contains a PDF-file for the theoretical parts and

source files (no executables or object files) for the programming assignments. The source files need to

include a makefile. Programming assignments need to be handed in as C, C++, or Python code. Please

write your own code. It is ok to take snippets from online resources, but they need to be clearly marked.