Unit 2
Sorting:- Type of Sorting, Bubble Sort, Selection Sort, Insertion Sort, Binary Insertion Sort, Shell Sort, Quick Sort, Merge Sort, Heap, Heap Sort. Sorting in Linear Time:- Counting Sort, Radix Sort, Bucket Sort.
University Questions are from
(AKTU, IPU, DTU, MDU, LPU, VIT, SRM, Amity, PU, JMI and many more…)
Design & Analysis of Algorithm
Assignment 1
Q – Explain types of sorting?
Q – What is internal sort? How it is different from external sort?
Q – How divide and conquer works?
Q – What is stable sorting? Is merge sort a stable sorting?
Q – Explain the working of merge sort. In which case merge sort is fastest?
Design & Analysis of Algorithm
Assignment 2
Q – Name the sorting algorithm that is most practically used and also write its time complexity.
Q – Prove that worst-case running time of any comparison sort is Ω(nlogn).
Q – Write non-deterministic algorithm for sorting.
Q – What do you mean by stability of a sorting algorithm? Explain its application.
Q – Discuss any one sorting algorithm having linear time complexity.
Design & Analysis of Algorithm
Assignment 3
Q – Apply BUCKET-SORT algorithm on the following array:
0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.21, 0.12, 0.23, 0.68
Q – Show the steps in heap sort to arrange following data in non-decreasing order 1, 2, 5, 6, 9, 8, 7
Q – Define Sorting? Apply sorting in non-decreasing order using any algorithm other than insertion sort.
Input – 34, 23, 12, 56, 43, 23, 34, 72
Q – Apply Merge sort on the following array:Â Â
A= < 9, 16, 52, 5, 8, 25, 35, 50 >
Q – What is the time and space complexity of counting sort? Illustrate the operation of counting sort on array
A = {1, 6, 3, 3, 4, 5, 6, 3, 4, 5}
Design & Analysis of Algorithm
Assignment 4
Q – Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(αn) + T((1 – α)n) + cn, where a is a constant in the range 0 < α < 1 and c > 0 is also a constant.
Q – Explain the working of shell sort? How it is related to insertion sort.
Q – How can you modify Quick Sort algorithm to search an item in a list?
Q – Why the space complexity of counting sort is O(n). Is it true that reducing time complexity increases space complexity?
Q – illustrate the operation of heap sort on the array A = (6, 1, 2, 4, 3, 5, 7, 9, 8, 0)
Design & Analysis of Algorithm
Assignment 5
Q – Among Merge sort, Insertion sort and quick sort which sorting technique is the best in worst case. Apply the best one among these algorithms to sort the list E, X, A, M, P, L, E in alphabetic order.
Q – Why is the worst-case complexity in quick sort is quadratic?
Q – In which case quick sort is fastest and how?
Q – Explain the working of bucket sort in detail.
Q – Explain the working of radix sort in detail.
Design & Analysis of Algorithm
Assignment 6
Q – Write non-recursive algorithm for quick sort.
Q – Prove that the worst-case running time of any comparison sort is Ω(nlogn).
Q – Describe any one of the following sorting techniques:
(i) Selection Sort
(ii) Insertion Sort
Q – What is the procedure of partition (A, p, r) in quick sort and also define the complexity of quick sort.
Q – How both the minimum and the maximum of a set of n elements can be computed in at most 3*floor(n/2) comparison?
Design & Analysis of Algorithm
Assignment 7
Q – Prove that Heapsort and Merge sort are optimal comparison sorting algorithms.
Q – Sort the following array using heap sort techniques:
{5, 13, 2, 25, 7, 17, 20, 8, 4}. Discuss its worst case and average case time complexities.
Q – Explain and write partitioning algorithm for quick sort.
Q – Write an algorithm for bucket sort.
Q – Apply BUCKET-SORT algorithm on the following array:
0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.21, 0.12, 0.23, 0.68
Design & Analysis of Algorithm
Assignment 8
Q – Differentiate between divide-&-conquer and partition method?
Q – Write the time complexity and space complexity of given sorting
- Insertion Sort
- Bubble Sort
- Selection Sort
- Heap Sort
- Merge Sort
- Quick Sort
- Shell Sort
Q – Prove that worst-case running time of any comparison sort is Ω(nlogn).
Q – Discuss any one sorting algorithm having linear time complexity.
Q – Define binary heap.
Design & Analysis of Algorithm
Assignment 9
Q – Discuss the best-case and worst-case complexities of the quick sort algorithm in detail.
Q – Write the merge sort algorithm for sorting a set of n points. Draw the recursion tree for n = 13.
(1) How many levels are there in the tree?
(2) How many comparisons are done at each level in the worst case?
(3) What is the total number if comparisons needed?
(4) Generalize (1) to (3) for any n (assume n is power of 2) in terms of O().
Q – Sort the elements of the given array A using shell sort algorithm:
A = {20, 35, 18, 8, 14, 41, 3, 39}
Q – Write non-deterministic algorithm for sorting.
Q – What do you understand by stable sort? Name two stable sort algorithms.
Design & Analysis of Algorithm
Assignment 10
Q – Apply Merge sort on the following array:Â
A= < 9, 16, 52, 5, 8, 25, 35, 50 >
Q – List out the disadvantages of divide and conquer algorithm.
Q – Write an algorithm for counting sort? Illustrate the operation of counting sort on the following array:
A = {4, 0, 2, 0, 1, 3, 5, 4, 1, 3, 2, 3}
Q – Explain the concepts of quick sort method and analyze its complexity with suitable example.
Q – How can you modify quick sort algorithm to search an item in a list?
Design & Analysis of Algorithm
Assignment 11
Q – Name the sorting algorithm that is most practically used and also write its time complexity.
Q – Apply Merge sort, Insertion sort and quick sort which sorting technique is the best in worst case. Apply the best one among these algorithms to sort the list E, X, A, M, P, L, E in alphabetic order.
Q – Explain heap on the array. Illustrate the operation of HEAP-SORT on the array
A = {6, 14, 3, 25, 2, 10, 20, 7, 6}
Q – Explain the working of counting sort in detail.
Illustrate the operation of counting sort on the following array:
A = {0, 1, 3, 0, 3, 2, 4, 5, 2, 4, 6, 2, 2, 3}.
Q – Apply BUCKET-SORT algorithm on the following array:
0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.21, 0.12, 0.23, 0.68
Design & Analysis of Algorithm
Assignment 12
Q – Describe any one of the following sorting techniques:
(i) Selection Sort
(ii) Insertion Sort
Q – How will you sort following array A of elements using heap sort. A = {23, 9, 18, 45, 5, 9, 1, 17, 6}
Q – Explain Merge sort algorithm and sort the following sequence {23, 11, 5, 15, 68,31, 4, 17} using merge sort. Q – Explain and compare best and worst time complexity of Quick Sort.
Q – Write three sorting algorithms that is linear in complexity.