Description
3 attachmentsSlide 1 of 3attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3
Unformatted Attachment Preview
Question 6: Lower Bounds and Linear time Sorting
• (a) A set of n natural numbers are uniformly distributed in the range 1 < x < Vn. Determine the
runtime (in big-Theta notation) of Counting Sort and Radix Sort. Find the expected runtime of Bucket
sort using 10 buckets. Which algorithm has the best asymptotic runtime?
(b) Given a set of three numbers {a,b,c} draw the comparison-based decision tree that represents the
execution of bubble-sort. Justify the length of the longest-path in your tree, using the results of problem
5 from practice set 1.
4
Figure for problem lc: Below shows one step of the girls sorting process. Examining bears 5 and 1, she
decides they need to be swapped. Then she moves left and will examine bears 4 and 1 next.
Problem 5:
You may have already come across another simple sorting algorithm called Bubble-sort. Instead of
describing the algorithm here, you are asked to do a bit of online research. One great place to start is here:
https://www.youtube.com/watch?v=lyZQP JUT5B4
Write the basic pseudo-code for Bubble sort, using comparisons and swaps. Determine the worst-case
number of swaps and the worst-case number of comparisons. Repeat for the best-case.
Problem 5
Assume that the input to Bubble sort is an array A indexed from 1 to n. The algorithm below passes through the elements
of the array and swaps any two adjacent elements that are not in relative order. The process continues until a full pass can
be made without any swaps.
made-swap = true
while(made-swap)
made-swap = false
for i = 1 to n-1
if A[i+1] < A[i]
Swap A[i] and A[i+1]
made-swap = true
Worst-case: Note that in the above algorithm, each execution of the for-loop carries out exactly n-1 comparisons. If the
array is sorted in reverse order, then after each pass of Bubblesort the maximum element of the unsorted section is moved
into the last position. For example, starting with 5, 4, 3, 2, 1 after one pass of bubble-sort the array becomes: 4,3,2,1,5,
and after the second pass the array becomes 3, 2, 1,4,5. Each pass places exactly one element in its final sorted position,
and therefore n passes are needed. Each pass performs exactly n 1 comparisons, and therefore the worst-case number of
comparisons is n(n-1). The number of swaps made during the first pass is n-1, during the second is n-2, etc. Therefore
the total number of swaps is n(n-1)/2 in the worst case.
Best-case: Bubblesort is effective if it is given an array that is already sorted. It is able to detect this right away, and
return the sorted array after one pass. This is because on a sorted array, 1, 2, 3, 4, 5, Bubblesort performs no swaps on the
first pass, and therefore will not repeat a second pass. Therefore the best-case number of swaps is 0 and the best-case number
of comparisons is n - 1.
Purchase answer to see full
attachment
Tags:
algorithms
lower bounds
inear time Sorting
User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.
