Sorting Algorithms - Answers
Section-A
1. 1. Define sorting and Why sorting is important?
Sorting is the process of arranging data in a particular order (ascending or descending).
Importance:
- Enhances data searching and retrieval.
- Makes data more readable and organized.
- Essential for algorithms like binary search.
2. 2. Explain the types of Sorting in detail.
- Bubble Sort: Compares adjacent elements and swaps them if in the wrong order.
- Selection Sort: Selects the minimum element and places it at the beginning.
- Insertion Sort: Inserts elements in the correct position one by one.
- Merge Sort: Uses divide and conquer to divide the array and merge in sorted form.
- Quick Sort: Uses a pivot to partition the array and recursively sorts.
- Heap Sort: Builds a heap and extracts the max/min element to sort.
3. 3. What is the role of the pivot element in the Quick Sort algorithm?
The pivot is used to partition the array into two halves where one side contains elements
less than the pivot and the other side contains elements greater than the pivot. It helps in
recursive division for sorting.
4. 4. Define Bubble Sort, Selection Sort and Insertion Sort.
- Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.
- Selection Sort: Selects the smallest element and places it at the beginning in each iteration.
- Insertion Sort: Builds the sorted array one element at a time by inserting elements into
their correct position.
5. 5. Define Heap Sort, Merge Sort and Quick Sort.
- Heap Sort: Converts array into a heap and extracts root repeatedly to sort.
- Merge Sort: Divides array into halves, sorts them recursively and merges them.
- Quick Sort: Chooses pivot, partitions array around pivot, recursively sorts partitions.
6. 6. What is the worst-case time complexity of the Bubble Sort, Heap Sort and Quick Sort
algorithm?
- Bubble Sort: O(n²)
- Heap Sort: O(n log n)
- Quick Sort: O(n²)
Section-B
7. 7. Write an algorithm for Bubble Sort and Merge Sort
Bubble Sort:
for i from 0 to n-1
for j from 0 to n-i-1
if array[j] > array[j+1]
swap array[j] and array[j+1]
Merge Sort:
mergeSort(arr):
if length of arr > 1
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
merge L and R into arr
8. 8. Write an algorithm for Selection Sort and Insertion Sort
Selection Sort:
for i from 0 to n-1
min_index = i
for j from i+1 to n
if array[j] < array[min_index]
min_index = j
swap array[i] and array[min_index]
Insertion Sort:
for i from 1 to n-1
key = array[i]
j=i-1
while j >= 0 and array[j] > key
array[j + 1] = array[j]
j=j-1
array[j + 1] = key
Section-C
9. 9. Sort the following list using Bubble Sort, Merge Sort and Quick Sort (44, 33, 55, 77, 90,
40, 60, 99, 22, 88, 66)
Sorted Result: 22, 33, 40, 44, 55, 60, 66, 77, 88, 90, 99
10. 10. Sort the following list using Heap Sort, Selection Sort and Insertion Sort (44, 33, 11,
55, 77, 90, 40, 60, 99, 22, 88, 66, 56, 12, 30)
Sorted Result: 11, 12, 22, 30, 33, 40, 44, 55, 56, 60, 66, 77, 88, 90, 99
Section-D
11. 11. Write the algorithm for Heap Sort and Quick Sort. Then sort (27, 38, 39, 33, 22, 18, 7,
15)
Heap Sort:
- Build max heap
- Swap first and last elements
- Reduce heap size and heapify root
- Repeat
Quick Sort:
- Choose pivot
- Partition array
- Recursively quicksort left and right subarrays
Sorted Result: 7, 15, 18, 22, 27, 33, 38, 39
12. 12. Sort the following list using Selection, Bubble, Merge, and Insertion Sort (23, 78, 45,
8, 32, 56, 14, 21)
Sorted Result: 8, 14, 21, 23, 32, 45, 56, 78
