Scribd
Upload
17 views

Tutorial Week-6 Set-1 Solution

The document discusses sorting algorithms like merge sort, quicksort, radix sort and bucket sort. It provides pseudocode for these algorithms and questions to analyze their time complexities. For merge sort, the recurrence relation and average number of comparisons for merging two sorted lists of length 2 is asked. For quicksort, the recurrence relations and relationship between number of comparisons for different input orders is asked. Radix sort and bucket sort are also explained with questions on implementing them and calculating their time complexities.

Uploaded by

devc96048
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views

Tutorial Week-6 Set-1 Solution

The document discusses sorting algorithms like merge sort, quicksort, radix sort and bucket sort. It provides pseudocode for these algorithms and questions to analyze their time complexities. For merge sort, the recurrence relation and average number of comparisons for merging two sorted lists of length 2 is asked. For quicksort, the recurrence relations and relationship between number of comparisons for different input orders is asked. Radix sort and bucket sort are also explained with questions on implementing them and calculating their time complexities.

Uploaded by

devc96048
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

School of Computer Science Engineering and Technology

Course- B. Tech Type- Core Course


Code- CSET206 Course Name-DAA
Year- 2024 Semester- Even
Date-15 -02-2024 Batch- 2022-2026

CO-Mapping

CO1 CO2 CO3


Q1 √
Q2 √
Q3 √

Objectives

1. Students will learn how to solve problems based on Quick sort, Merge
Sort, Radix sort and Bucket sort.

Solutions:

1.
Merge sort Pseudocode:
MERGE-SORT (A,p,r)
a. If p<r
b. q= ⌊(p+r)/2⌋
c. MERGE-SORT (A,p,q)
d. MERGE-SORT (A,q+1,r)
e. MERGE (A,p,q,r)
i) Write a recurrence relation of the above Pseudocode and calculate the time complexity.
ii) The average no of comparison performed by merge sort algorithm, in merging 2 sorted
lists of length 2 is _______________________.
2.
Quicksort is running on two inputs as shown below:
a) 1,2,3,……..,n
b) n, n-1, n-2,….,2,1
i) Write the recurrence relations for the two inputs and calculate time complexity.
ii) If C1 and C2 be the number of comparisons made for a) and b). What is the relation
between C1 and C2.

3.
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using
an O(n) time algorithm.
Write the recurrence relation of the above case and what is the time complexity.
4.
Algorithm:
a. RadixSort(arr)
b. max = largest element in the given array
c. d = number of digits in the largest element (or, max)
d. Now, create d buckets of size 0 - 9
e. for i -> 0 to d
f. sort the array elements using counting sort (or any stable sort) according to the digits at
the i th place.

i) Use radix sort to sort elements in given array.


A={181,289,390,121,145,736,514,212}
ii)Suppose ‘m’ is the maximum number in base B and n is the number of elements in array.
What is the time complexity.
iii) Sort array of ‘n’ int represented in decimal number system and maximum element is
having 10 digits. What is the time complexity?

5.
A=[0.79, 0.13, 0.64, 0.39, 0.20, 0.89, 0.53, 0.42, 0.06, 0.94]
B=[0.79, 0.78, 0.710, 0.707]
BUCKET-SORT (A)
let A’ [0, …., n-1] be a new array
n=A.length
for i=0 to n-1
make A’[i] an empty list
for i=1 to n
insert A[i] into list A’[⌊nA[i]⌋]
for i=0 to n-1
If A’[i] holds more than one elements
sort A’[i] with insertion sort
concatenate the list together A’[0], A’[1], ….., A’[n-1] (in order)

i) Use the above algorithm to sort array A and B.


ii) What is the time complexity for both cases in generalized term?

You might also like