Data Structures and Algorithms · Unit 6 · 8 hrs
Sorting
Exam-focused notes for Sorting (Data Structures and Algorithms, CSC211): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Introduction and Types of sorting: Internal and External sort
- Comparison Sorting Algorithms: Bubble, Selection and Insertion Sort, Shell Sort
- Divide and Conquer Sorting: Merge, Quick and Heap Sort
- Efficiency of Sorting Algorithms
Comparison Sorting Algorithms
Sort the number {82, 73, 12, 39, 26, 88, 2, 9, 60, 41} using shell sort. [5]
Index 0 1 2 3 4 5 6 7 8 9 ------------------------------------- Value 82 73 12 39 26 88 2 9 60 41 - $n = 10$ - Increment sequence chosen: $k = 5, 2, 1$ (standard $n/2$ halving) Sub-files (elements 5 positions apart): Sub-file Indices Values Sorted ---------...
Full solved answer →Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11. [5]
Array to sort (9 elements): $$[2,\ 81,\ 6,\ 45,\ 11,\ 21,\ 23,\ 41,\ 11]$$ Index 0 1 2 3 4 5 6 7 8 ----------------------------------------- Value 2 81 6 45 11 21 23 41 11 All data present. Sorting ascending. --- Method: Selection sort finds the minimum in ...
Full solved answer →Write a program to implement insertion sort. [5]
Insertion sort builds the sorted array one element at a time by picking each element and inserting it into its correct position among the already-sorted elements. The worst case time complexity is O(n²), but best case is O(n) (already sorted array). --- ---...
Full solved answer →Sort the numbers 82, 73, 12, 39, 26, 88, 2, 9, 60, 41 using shell sort. [5]
Array (n = 10), 1-indexed: Index 1 2 3 4 5 6 7 8 9 10 -------------------------------------- Value 82 73 12 39 26 88 2 9 60 41 Increment sequence chosen: $k = 5, 3, 1$ (the standard textbook choice $\lfloor n/2 \rfloor, \dots$; here fixed to 5, 3, 1 as comm...
Full solved answer →Hand test selection sort with array of numbers 4, 71, 32, 19, 61, 2, -5 in descending order. [5]
Given data: - Array: $[4, 71, 32, 19, 61, 2, -5]$ - Number of elements: $n = 7$ - Sort order: Descending - Algorithm: Selection Sort --- Selection sort (descending): In each pass, find the largest element in the unsorted portion and swap it to the front of ...
Full solved answer →Hand test bubble sort with array of numbers 53, 42, 78, 3, 5, 2, 15 in ascending order. [5]
Array (7 elements): $53, 42, 78, 3, 5, 2, 15$ Task: Sort in ascending order using bubble sort. Rule: Compare adjacent pairs $a[i]$ and $a[i+1]$; swap if $a[i] a[i+1]$. After each pass, the largest unsorted element bubbles to its correct position. --- Compar...
Full solved answer →What do you mean by sorting? Explain the Bubble sort with example. [5]
Sorting is the process of arranging data elements in a specific order (either ascending or descending) so that the data can be searched, accessed, or processed more efficiently. Sorting organizes a collection of data into a sequence ordered by some criterio...
Full solved answer →Divide and Conquer Sorting
In which case the position of pivot element in quick sort always either in the last or the first position? Create a max heap from the numbers {10,12,53,34,23,77,59,66,5,8}. [5]
- Numbers to build max heap: $\{10, 12, 53, 34, 23, 77, 59, 66, 5, 8\}$ (10 elements) --- The pivot ends up in the first or last position after partitioning when the array is already sorted (ascending or descending), assuming the pivot is chosen as the firs...
Full solved answer →Write short notes on: a. Divide and Conquer sorting b. AVL Tree [5]
--- Divide and Conquer is an important problem-solving technique that makes use of recursion. It consists of two main parts: - Divide: The original problem is broken into smaller sub-problems, which are solved recursively. - Conquer: The solutions to the su...
Full solved answer →Explain concept of divide and conquer algorithm. Hand test quick sort algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19). What is time complexity of quick sort algorithm?[10]
- Array to sort: $(78, 34, 21, 43, 7, 18, 9, 56, 38, 19)$, 10 elements. - Tasks: explain divide and conquer, hand-test quick sort, state time complexity. --- Divide and conquer is an algorithm design paradigm that solves a problem by recursively breaking it...
Full solved answer →Make Unit 6 stick
Practice CSC211 with flashcards & quizzes