Sale!

# Data Structures and Algorithms Written Assignment Two

\$30.00

Ve281 Data Structures and Algorithms
Written Assignment Two
The assignment consists of five problems.
1. Sort 3, 7, 4, 1, 8, 9, 2, 6, 5, 10 using quick sort. The pivot is chosen as the median
of the first, the middle (or the left-to-middle element if the array size N is even), and
the last element. Use the in-place partitioning strategy discussed in class (Note that
you should swap the selected pivot with the first element of the array as the first step
of the partitioning). Assume that if the subarray size is less than or equal to three,
insertion sort will be called to sort the subarray. Show the intermediate steps, such
as the pivot you choose, the array after partitioning, etc. Do not just write the final
sorted result.

Category:

## Description

Ve281 Data Structures and Algorithms
Written Assignment Two
The assignment consists of five problems.
1. Sort 3, 7, 4, 1, 8, 9, 2, 6, 5, 10 using quick sort. The pivot is chosen as the median
of the first, the middle (or the left-to-middle element if the array size N is even), and
the last element. Use the in-place partitioning strategy discussed in class (Note that
you should swap the selected pivot with the first element of the array as the first step
of the partitioning). Assume that if the subarray size is less than or equal to three,
insertion sort will be called to sort the subarray. Show the intermediate steps, such
as the pivot you choose, the array after partitioning, etc. Do not just write the final
sorted result.
2. Apply radix sort to sort the sequence of decimal numbers 189, 479, 032, 538, 446, 526,
943, 738, 632, 379. Show the intermediate steps. Do not just write the final sorted
result.
3. In the deterministic linear-time selection algorithm, instead of partitioning all the
inputs into a number of groups of size 5, we partition the inputs into a number of
groups of size 7. The rest steps of the algorithm are similar to the original version.
Will the runtime of this new algorithm still be O(n), where n is the input size? Prove