CHAPTER 5: SORTING

5.1 Introduction
• Sorting is the process of arranging elements in a particular order (ascending, descending, alpha-
betical, etc.).
• It is essential for easy data retrieval and efficient searching.
• Common applications:
– Dictionaries (alphabetical order)
– Exam seating plans (roll number order)
– Sorting by height, weight, etc.

5.2 Bubble Sort

Concept
• Compares adjacent elements and swaps them if they are in the wrong order.
• After each pass, the largest unsorted element “bubbles up” to its correct position.
• Requires n – 1 passes for a list of size n.

Optimization Tip If no swaps occur in a pass, the list is already sorted — the algorithm can be
terminated early.
Diagram: Bubble Sort Passes We will sort:
[8, 7, 13, 1, -9, 4]
Each pass compares adjacent elements and swaps if needed.

Pass 1
[8, 7, 13, 1, -9, 4]
→ Swap 8 and 7 → [7, 8, 13, 1, -9, 4]
→ No Swap (8,13)
→ Swap 13 and 1 → [7, 8, 1, 13, -9, 4]
→ Swap 13 and -9 → [7, 8, 1, -9, 13, 4]
→ Swap 13 and 4 → [7, 8, 1, -9, 4, 13]

Pass 2
[7, 8, 1, -9, 4, 13]
→ No Swap (7,8)
→ Swap 8 and 1 → [7, 1, 8, -9, 4, 13]
→ Swap 8 and -9 → [7, 1, -9, 8, 4, 13]
→ Swap 8 and 4 → [7, 1, -9, 4, 8, 13]
Pass 3
[7, 1, -9, 4, 8, 13]
→ Swap 7 and 1 → [1, 7, -9, 4, 8, 13]
→ Swap 7 and -9 → [1, -9, 7, 4, 8, 13]
→ Swap 7 and 4 → [1, -9, 4, 7, 8, 13]

Pass 4
[1, -9, 4, 7, 8, 13]
→ Swap 1 and -9 → [-9, 1, 4, 7, 8, 13]

Pass 5
No swaps → Sorting complete.
Final list: [-9, 1, 4, 7, 8, 13]

Algorithm 5.1: Bubble Sort

BUBBLESORT(numList, n)
1. Set i = 0
2. While i < n repeat:
3. Set j = 0
4. While j < n - i - 1 repeat:
5. If numList[j] > numList[j+1], then
6. Swap numList[j] and numList[j+1]
7. j = j + 1
8. i = i + 1

Python Program
def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
5.3 Selection Sort
Concept
• The list is divided into sorted and unsorted parts.
• The smallest element from the unsorted list is selected and swapped with the first unsorted element.
• Requires n – 1 passes for n elements.
Diagram: Selection Sort Passes Starting List: [8, 7, 13, 1, -9, 4]
Pass 1 - Smallest is -9 → Swap with 8
[-9, 7, 13, 1, 8, 4]
Pass 2 - Smallest in [7,13,1,8,4] is 1 → Swap with 7
[-9, 1, 13, 7, 8, 4]
Pass 3 - Smallest in [13,7,8,4] is 4 → Swap with 13
[-9, 1, 4, 7, 8, 13]
Pass 4 - Smallest in [7,8,13] is 7 (already in place)
[-9, 1, 4, 7, 8, 13]
Pass 5 - Already sorted
[-9, 1, 4, 7, 8, 13]
Algorithm 5.2: Selection Sort
SELECTIONSORT(numList, n)
1. Set i = 0
2. While i < n repeat:
3. Set min = i, flag = 0
4. Set j = i + 1
5. While j < n repeat:

6. If numList[j] < numList[min]:

7. min = j
8. flag = 1
9. If flag == 1:
10. Swap numList[i], numList[min]
11. i = i + 1
Python Program
def selection_Sort(list2):
n = len(list2)
for i in range(n):
min = i
for j in range(i + 1, n):
if list2[j] < list2[min]:
min = j
list2[i], list2[min] = list2[min], list2[i]
numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
5.4 Insertion Sort
Concept
• Elements from the unsorted part are picked and inserted into the correct position of the sorted part.
• Like arranging cards in hand.
Diagram: Insertion Sort Passes Initial List: [8, 7, 13, 1, -9, 4]
Pass 1 Insert 7 into sorted [8]
[7, 8, 13, 1, -9, 4]
Pass 2 Insert 13 into sorted [7,8]
[7, 8, 13, 1, -9, 4]
Pass 3 Insert 1 into sorted [7,8,13]
[1, 7, 8, 13, -9, 4]
Pass 4 Insert -9 into sorted [1,7,8,13]
[-9, 1, 7, 8, 13, 4]
Pass 5 Insert 4 into sorted [-9,1,7,8,13]
[-9, 1, 4, 7, 8, 13]

Algorithm 5.3: Insertion Sort

INSERTIONSORT(numList, n)
1. Set i = 1
2. While i < n repeat:
3. temp = numList[i]
4. Set j = i - 1
5. While j >= 0 and numList[j] > temp:
6. numList[j+1] = numList[j]
7. j = j - 1
8. numList[j+1] = temp
9. i = i + 1
Python Program
def insertion_Sort(list3):
n = len(list3)
for i in range(n):
temp = list3[i]
j = i-1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[j]
j -= 1
list3[j+1] = temp

numList = [8, 7, 13, 1, -9, 4]

insertion_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
5.5 Time Complexity of Algorithms
Basic Complexity Concepts
• Constant Time (O(1)): No loops.
• Linear Time (O(n)): Single loop.
• Quadratic Time (O(n²)): Nested loops.

All three sorting algorithms in this chapter (bubble, selection, insertion) have O(n²) complexity due to
nested loops.
 MCQs
1. Which of the following sorting techniques is based on repeatedly comparing adjacent ele-
ments and swapping them if they are in the wrong order?
A) Selection Sort
B) Bubble Sort
C) Insertion Sort
D) Merge Sort

Answer: B) Bubble Sort

2. What is the time complexity of Bubble Sort in the worst-case scenario?

A) O(n) B)O(log n) C) O(n²) D) O(n log n)

Answer: C) O(n²)

3. Which of the following best describes the logic of the Bubble Sort algorithm?
A) Select the smallest element and place it in the beginning.
B) Insert the current element into its correct position in a sorted list.
C) Swap adjacent elements until the largest reaches the end.
D) Divide the list and merge sorted parts.

Answer: C) Swap adjacent elements until the largest reaches the end.

4. How many passes are required to sort a list of 6 elements using Bubble Sort?

A) 5 B) 6 C) 4 D) 3

Answer: A) 5

5. Which sorting technique finds the smallest element in the list and places it in its correct po-
sition?

A) Insertion Sort B) Bubble Sort C) Selection Sort D)Quick Sort

Answer: C) Selection Sort

6. In Selection Sort, after the first pass, the first element of the list is:
A) The largest element
B) The average of the list
C) The smallest element
D) Unchanged

Answer: C) The smallest element

7. What is the time complexity of Selection Sort in the best case?

A) O(n log n) B)O(n²) C)O(n) D)O(log n)

Answer: B) O(n²)
8. Which sorting technique is best described as “a sorted list is built one element at a time”?
A) Merge Sort B)Insertion Sort C)Bubble Sort D)Selection Sort

Answer: B) Insertion Sort

9. In Insertion Sort, which of the following is TRUE about the sorted portion of the list?
A) It decreases in size
B) It is built from left to right
C) It always remains constantIt is sorted in reverse order

Answer: B) It is built from left to right

 10. What is the best-case time complexity of Insertion Sort?
A) O(n log n) B)O(n) C)O(n²) D)O(1)

Answer: B) O(n)

11. Which sorting algorithm is generally better for nearly sorted data?
A) Selection Sort B)Bubble Sort C)Insertion Sort D)Heap Sort

Answer: C) Insertion Sort

12. In Bubble Sort, which element reaches its correct position after the first pass?
A) The smallest element B)The middle element C)The largest element D)The second
largest element

Answer: C) The largest element

13. Which sorting algorithm swaps elements only when necessary and avoids unnecessary move-
ments?

A) Bubble Sort
B) Insertion Sort
C) Selection Sort
D) None of the above

Answer: C) Selection Sort

14. Which of the following algorithms uses a temporary variable during swapping?

A) Bubble Sort
B) Selection Sort
C) Insertion Sort
D) All of the above

Answer: D) All of the above

15. Which sort algorithm is not** efficient for large datasets?**

A) Quick Sort
B) Insertion Sort
C) Merge Sort
D) Heap Sort

Answer: B) Insertion Sort

16. In the Insertion Sort algorithm, when is shifting required?

A) When the current element is greater than the previous one
B) When the current element is smaller than elements in the sorted list
C) When elements are equal
D) Always

Answer: B) When the current element is smaller than elements in the sorted list

17. The number of comparisons in the worst case for Bubble Sort is:

A) n
B) n-1
C) n(n-1)/2
D) log n

Answer: C) n(n-1)/2

18. Which sorting algorithm is described using the following pseudocode?

 For i = 0 to n-2:
For j = 0 to n-2-i:
If arr[j] > arr[j+1]:
Swap arr[j] and arr[j+1]

A) Insertion Sort
B) Bubble Sort
C) Selection Sort
D) Quick Sort

Answer: B) Bubble Sort

19. Which sorting method has the same time complexity in best, average, and worst cases?
A) Selection Sort
B) Insertion Sort
C) Merge Sort
D) Bubble Sort

Answer: A) Selection Sort

20. In Selection Sort, if the minimum element is already at its correct position, what happens?
A) The list is reversed
B) The algorithm stops
C) No swap is made
D) Swap still happens

Answer: C) No swap is made

21. Assertion (A): Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
Reason (R): Bubble Sort pushes the smallest element to the end in each pass.

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.
Answer: C. A is true, but R is false.
Explanation: Bubble Sort pushes the largest element to the end of the list in each pass, not the small-
est.
22. Assertion (A): In Selection Sort, the smallest element is selected in each pass and placed in its
correct position.
Reason (R): Selection Sort uses repeated shifting of elements to sort the list.
A. Both A and R are true, and R is the correct explanation of A.
B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: C. A is true, but R is false.

Explanation: Selection Sort works by swapping, not shifting elements.
23. Assertion (A): Insertion Sort is efficient for nearly sorted lists.
Reason (R): In the best case, the time complexity of Insertion Sort is O(n).

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: A. Both A and R are true, and R is the correct explanation of A.

24. Assertion (A): Selection Sort is a stable sorting algorithm.
 Reason (R): Selection Sort preserves the order of identical elements.

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is false, but R is true.
D. Both A and R are false.
Answer: D. Both A and R are false.
Explanation: Selection Sort is not stable by default and may change the relative order of identical ele-
ments.
25. Assertion (A): Insertion Sort builds the final sorted list one item at a time.
Reason (R): It inserts each new element at the beginning of the list.

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: C. A is true, but R is false.

Explanation: Insertion Sort inserts elements into the correct position within the sorted portion, not
necessarily at the beginning.
26. Assertion (A): Bubble Sort can be optimized to stop early if no swaps are made during a pass.
Reason (R): This optimization improves its best-case time complexity to O(n).

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: A. Both A and R are true, and R is the correct explanation of A.

27. Assertion (A): In Bubble Sort, every pair of adjacent elements is compared in each pass.
Reason (R): The number of comparisons increases with each pass.
A. Both A and R are true, and R is the correct explanation of A.
B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: C. A is true, but R is false.

Explanation: The number of comparisons decreases with each pass in Bubble Sort.

28. Assertion (A): In Selection Sort, the number of comparisons is always the same regardless of the
input order.
Reason (R): Selection Sort has a time complexity of O(n²) for all cases.

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: A. Both A and R are true, and R is the correct explanation of A.

29. Assertion (A): In Insertion Sort, shifting elements is necessary to maintain the sorted portion of the
list.
Reason (R): Elements are shifted right to make space for the current element.
A. Both A and R are true, and R is the correct explanation of A.
B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.
Answer: A. Both A and R are true, and R is the correct explanation of A.
30. Assertion (A): All three sorting techniques (Bubble, Selection, Insertion) have a worst-case time
com- plexity of O(n²).
Reason (R): They all use nested loops with two iterations each.

A. Both A and R are true, and R is the correct explanation of A.

B. Both A and R are true, but R is not the correct explanation of A.
C. A is true, but R is false.
D. A is false, but R is true.

Answer: A. Both A and R are true, and R is the correct explanation of A.

FILL IN THE BLANKS
1. Sorting is the process of arranging elements in a particular .
Answer: order

2. In Bubble Sort, after each pass, the element gets placed at its correct position.
Answer: largest
3. In Bubble Sort, the process of comparing and swapping adjacent elements is repeated for
- 1 passes.
Answer: n
4. If no are made during a pass in Bubble Sort, the list is already sorted.
Answer: swaps
5. In Selection Sort, the list is conceptually divided into a list and an unsorted list.
Answer: sorted
6. In each pass of Selection Sort, the element from the unsorted portion is selected and
placed in the sorted list.
Answer: smallest
7. Selection Sort requires a total of - 1 passes to sort a list of n elements.
Answer: n
8. In Insertion Sort, each element from the unsorted list is into its correct position in the
sorted part.
Answer: inserted
9. In Insertion Sort, shifting of elements occurs from to find the correct position of insertion.
Answer: right to left
10. In the best-case scenario, Insertion Sort has a time complexity of .
Answer: O(n)
11. The time complexity of Bubble, Selection, and Insertion Sort in the worst case is .
Answer: O(n²)
12. A loop is responsible for increasing the time complexity of sorting algorithms to
quadratic.
Answer: nested
13. Sorting helps to improve the efficiency of operations on large datasets.
Answer: searching
14. In Python, a pair of adjacent elements in Bubble Sort can be swapped using the syntax:
list[j], list[j+1] =
Answer: list[j+1], list[j]
15. The algorithm that builds the sorted list one element at a time by comparing and shifting is
Sort.
Answer: Insertion