Data Structures and Algorithms · Unit 6
Sorting Algorithms
Exam-focused notes for Sorting Algorithms (Data Structures and Algorithms, BIT201): what the TU syllabus asks and how it has actually been tested, with 5 solved past questions from this unit.
What this unit covers
- Sorting problem definition
- Quick sort algorithm and tracing
- Quick sort time complexity analysis
- Pivot selection and limitations
- Merge sort algorithm and tracing
- Merge sort time complexity analysis
- Why sorting is needed
Why sorting is needed
Why do we need sorting?Trace the Quick sort for the input {12, -9, 56, 23, 4, 8, 6, 9, 23, 21}.[2+8]
(a) Why Do We Need Sorting? Sorting arranges data in a defined order (ascending or descending). We need it because: 1. Faster searching: Sorted data enables Binary Search ($O(\log n)$) instead of linear search ($O(n)$). 2. Data organization/presentation: Ea...
Full solved answer →Merge sort algorithm and tracing
Discuss the limitation of choosing first element as pivot in quick sort. Using merge sort algorithm, sort the numbers 40, 6, 5,21, 3, 100, 90, 7, 8, 12, 30.[10]
- Array to sort: 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30 (11 elements) - Sorting method: Merge Sort - Discussion topic: limitation of first-element pivot in Quick Sort --- Quick Sort selects a pivot and partitions the array into elements smaller and larger t...
Full solved answer →Explain merge sort along with its time complexity. Use this algorithm to sort array of numbers given below: 25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11[10]
Array to sort (n = 13): $$[25,\ 37,\ 48,\ 25,\ 23,\ 17,\ 31,\ 45,\ 7,\ 21,\ 15,\ 8,\ 11]$$ Indices 0 to 12. No values missing; all data is readable. --- Merge Sort is a divide and conquer algorithm. It: - Divides the array into two halves. - Conquers by rec...
Full solved answer →Quick sort algorithm and tracing
Explain quick sort algorithm. Use this algorithm to sort the numbers 35, 82, 18, 54, 13, 31, 20, 69, and 19.[10]
Quick Sort is a divide-and-conquer sorting algorithm. It selects a pivot element and partitions the array so that all elements less than or equal to the pivot are on its left, and all greater elements are on its right. The pivot is then in its final sorted ...
Full solved answer →Define sorting problem. Trace quick sort algorithm for the following given list of data and also discuss about its time complexity: 78 45 23 89 65 12 90 33[10]
The sorting problem is stated as: - Input: A sequence of $n$ numbers $\langle a1, a2, \dots, an \rangle$. - Output: A permutation (rearrangement) $\langle a1', a2', \dots, an' \rangle$ of the input such that $a1' \le a2' \le \dots \le an'$. That is, given a...
Full solved answer →Make Unit 6 stick
Practice BIT201 with flashcards & quizzes