CS2002 – DSA Assignment Number 4
CS2002 – Data Structures and Algorithms
Assignment Number 4
Spring 2025
Maximum Marks: 70 Due Date: 9 May 2025
CLO No. CLO Statement Domain Taxono
my
Level
4 Apply different sorting algorithms to sort the one Cognitiv 3
dimensional arrays. e
Question Number 1 (CLO 4) (10 marks) Apply the radix sort to sort the following array in
ascending order. Show all the steps while sorting the array.
82 901 100 12 150 77 55 23
National University of Computer and Emerging Sciences – FAST, CFD Campus 1
CS2002 – DSA Assignment Number 4
Question Number 2 (CLO 4) (10 marks) Apply the shell sort to sort the following array in
ascending order. Show all the steps while sorting the array.
35 33 42 10 14 19 27 44
First we take the interval of 4. Make a virtual sub-list of all values located at the interval
of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}
We compare values in each sub-list and swap them (if necessary) in the original array.
After this step, the new array should look like this:
Then, we take interval of 1 and this gap generates two sub-lists, which are given
as: {14, 27, 35, 42}, {19, 10, 33, 44}
We compare and swap the values, if required, in the original array. After this step, the
array should look like this
National University of Computer and Emerging Sciences – FAST, CFD Campus 2
CS2002 – DSA Assignment Number 4
Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion
sort to sort the array.
Following is the step-by-step depiction:
National University of Computer and Emerging Sciences – FAST, CFD Campus 3
CS2002 – DSA Assignment Number 4
Question Number 3 (CLO 4) (10 marks) Apply the cycle sort to sort the following array in
ascending order. Show all the steps while sorting the array.
3 2 1 4 6 5
National University of Computer and Emerging Sciences – FAST, CFD Campus 4
CS2002 – DSA Assignment Number 4
Question Number 4 (CLO 4) (10 marks) Apply the bucket sort to sort the following array in
ascending order. Show all the steps while sorting the array.
10 08 20 07 16 18 12 01 23 11
In first step, create buckets with a range from 0 to 25. The buckets range are 0-5, 5-10,
10- 15, 15-20, 20-25. Elements are inserted in the buckets according to the bucket range.
Suppose the value of an item is 16, so it will be inserted in the bucket with the range
15-20. Similarly, every item of the array will insert accordingly. This phase is known to
be the scattering of array elements.
Now, sort each bucket individually. The elements of each bucket can be sorted by using
any of the stable sorting algorithms.
At last, gather the sorted elements from each bucket in order
Now, the array is completely sorted.
National University of Computer and Emerging Sciences – FAST, CFD Campus 5
CS2002 – DSA Assignment Number 4
Question Number 5 (CLO 4) (10 marks) Apply the Tim sort to sort the following array in
ascending order. Show all the steps while sorting the array.
40 10 20 42 16 27 25 1 19
Divide the array in two halves
Sorting the left subarray
Sorting the right subarray
Sorted subarray
Unsorted subarray
Sorted subarray
Unsorted subarray
[40]
[10 20 42]
[27]
[25 1 19]
st
1 iteration a[1] = 10
4th iteration a[4] = 25
Sorted subarray
Unsorted subarray
Sorted subarray
Unsorted subarray
[10 40]
[20 42]
[25 27]
[1 19]
nd
2 iteration a[2] = 20
5th iteration a[2] = 1
Sorted subarray
Unsorted subarray
Sorted subarray
Unsorted subarray
[10 20 40]
[42]
[1 25 27]
[19]
rd
3 iteration a[3] = 42
6th iteration a[3] = 19
Sorted subarray
Unsorted subarray
Sorted subarray
Unsorted subarray
[10 20 40 42]
[]
[1 19 25 27]
[]
Now, merge both sorted subarrays to get the final array as -
Now, the array is completely sorted.
National University of Computer and Emerging Sciences – FAST, CFD Campus 6
CS2002 – DSA Assignment Number 4
Question Number 6 (CLO 4) (10 marks) Apply the comb sort to sort the following array in
ascending order. Show all the steps while sorting the array.
49 11 24 44 29 27 02 22
n=8
gap = n
shrink = 1.3
swapped = true
First iteration
gap = floor(gap/shrink) = floor(8/1.3) = 6
swapped = false
This
iteration ends here, because at i =2, the value of i + gap = 2 + 6 = 8, and there is no
element at 8th position of the array. So, after first iteration, the elements of array will be
Second iteration
gap = floor(gap/shrink) = floor(6/1.3) = 4
swapped = false
This
iteration ends here, because at i =4, the value of i + gap = 4 + 4 = 8, and there is no
element at 8th position of the array. So, after second iteration, the elements of array will
be
National University of Computer and Emerging Sciences – FAST, CFD Campus 7
CS2002 – DSA Assignment Number 4
Third iteration
gap = floor(gap/shrink) = floor(4/1.3) = 3
swapped = false
This
iteration ends here, because at i =5, the value of i + gap = 5 + 3 = 8, and there is no element
at 8th position of the array. So, after third iteration, the elements of array will be
Fourth iteration
gap = floor(gap/shrink) = floor(3/1.3) = 2
swapped = false
This
iteration ends here, because at i =6, the value of i + gap = 6 + 2 = 8, and there is no element
at 8th position of the array. So, after fourth iteration, the elements of array will be
National University of Computer and Emerging Sciences – FAST, CFD Campus 8
CS2002 – DSA Assignment Number 4
Fifth iteration
gap = floor(gap/shrink) = floor(2/1.3) = 1
swapped = false
After the fifth iteration, the sorted array is
Hence, the iterations end here, and now the sorting is completed. Now, the final sorted
array is
National University of Computer and Emerging Sciences – FAST, CFD Campus 9
CS2002 – DSA Assignment Number 4
Question Number 7 (CLO 4) (10 marks) Apply the counting sort to sort the following array
in ascending order. Show all the steps while sorting the array.
2 5 3 0 2 3 0 3
Step1 :
Find out the maximum element from the given array.
Step 2:
Initialize a countArray[] of length max+1 with all elements as 0. This array will be used
for storing the occurrences of the elements of the input array.
Step 3:
In the countArray[], store the count of each unique element of the input array at
their respective indices.
For Example: The count of element 2 in the input array is 2. So, store 2 at index 2 in
the countArray[]. Similarly, the count of element 5 in the input array is 1, hence store
1 at index 5 in the countArray[].
Step 4:
Store the cumulative sum or prefix sum of the elements of the countArray[] by doing
countArray[i] = countArray[i – 1] + countArray[i]. This will help in placing the
elements of the input array at the correct index in the output array.
Step 5:
Iterate from end of the input array and because traversing input array from end
preserves the order of equal elements, which eventually makes this sorting algorithm
stable. Update outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i]. Also,
update countArray[ inputArray[i] ] = countArray[ inputArray[i] ]– -.
National University of Computer and Emerging Sciences – FAST, CFD Campus 10
CS2002 – DSA Assignment Number 4
Step 6: For i = 6,
Update outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Also, update countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –
Step 7: For i = 5,
Update outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Also, update countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –
Step 8: For i = 4,
Update outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Also, update countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –
Step 9: For i = 3,
Update outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Also, update countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –
National University of Computer and Emerging Sciences – FAST, CFD Campus 11
CS2002 – DSA Assignment Number 4
Step 10: For i = 2,
Update outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Also, update countArray[ inputArray[2] ] = countArray[ inputArray[2] ]-
–
Step 11: For i = 1,
Update outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Also, update countArray[ inputArray[1] ] = countArray[ inputArray[1] ]-
–
Step 12: For i = 0,
Update outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Also, update countArray[ inputArray[0] ] = countArray[ inputArray[0] ]-
–
National University of Computer and Emerging Sciences – FAST, CFD Campus 12
