Revision Summary: Sorting (NCERT Class 12 CS)
1. Chapter at a Glance
- Sorting is the process of ordering a given collection of elements in a particular order (ascending/descending for numbers, alphabetical or by length for strings).
- Bubble sort repeatedly compares and swaps adjacent elements in n–1 passes; the largest element “bubbles up” to its correct position after each pass.
- Selection sort divides the list into a sorted left part and an unsorted right part; in each of n–1 passes it selects the smallest element from the unsorted part and swaps it with the leftmost unsorted element.
- Insertion sort also maintains a sorted and an unsorted part; each element from the unsorted part is inserted at its correct position in the sorted part by shifting larger elements right.
- All three algorithms perform n–1 passes for a list of n elements.
- A pass is one complete iteration through the required elements of the list.
- An optimisation for bubble sort: stop early if a pass produces no swaps (list is already sorted).
- Time complexity of bubble, selection and insertion sort is n² because each contains a nested loop.
2. Key Terms and Definitions
- Sorting: The process of ordering or arranging a given collection of elements in some particular order.
- Pass: Every iteration through each element of a list (in the context of these algorithms).
- Swapping: Changing the positions of two elements with each other.
- Bubble sort: Sorting technique that repeatedly compares adjacent elements and swaps them if they are unordered, causing the largest element to “bubble up” after each pass.
- Selection sort: Sorting technique that selects the smallest element from the unsorted part and swaps it with the leftmost element of the unsorted part in each pass.
- Insertion sort: Sorting technique that inserts each element of the unsorted part into its appropriate position in the sorted part by shifting elements right.
- Time complexity: The amount of time an algorithm takes to process a given data set.
- Constant time algorithm: Algorithm with no loops; executes a fixed number of instructions (time complexity = 1).
- Linear time algorithm: Algorithm with a single loop that runs n times (time complexity = n).
- Quadratic time algorithm: Algorithm containing a nested loop (time complexity = n²).
3. Syntax and Constructs
Python implementations (user-defined functions) given in the chapter:
python
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]
python
def selection_Sort(list2):
n = len(list2)
for i in range(n):
min = i
flag = 0
for j in range(i+1, n):
if list2[j] < list2[min]:
min = j
flag = 1
if flag == 1:
list2[min], list2[i] = list2[i], list2[min]
python
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 = j-1
list3[j+1] = temp
4. Algorithms and Worked Logic
Bubble Sort (Algorithm 5.1)
- For i from 0 to n–2:
– For j from 0 to n–i–2: compare list[j] and list[j+1]; swap if list[j] > list[j+1].
- Largest element reaches its final position after each pass; last i elements are ignored in subsequent passes.
Selection Sort (Algorithm 5.2)
- For i from 0 to n–2:
– Set min = i; scan j = i+1 to n–1; update min if a smaller element is found.
– Swap list[i] with list[min] if a smaller element was located.
- After each pass the next smallest element is placed at the beginning of the remaining unsorted part.
Insertion Sort (Algorithm 5.3)
- For i from 1 to n–1:
– Store list[i] in temp; set j = i–1.
– While j ≥ 0 and list[j] > temp: shift list[j] one position right (list[j+1] = list[j]), decrement j.
– Place temp at list[j+1].
- Each unsorted element is inserted into the already-sorted prefix.
5. Common Errors and Exam Pitfalls
- Forgetting that bubble/selection/insertion sort each require exactly n–1 passes and writing an off-by-one loop limit.
- Missing the early-termination condition (no swap in a pass) when asked to improve bubble sort.
- Incorrect inner-loop bound in bubble sort (should be n–i–1) leading to unnecessary or out-of-range comparisons.
- Forgetting to initialise
flag = 0 or min = i at the start of each outer iteration in selection sort.
- In insertion sort, writing the while condition without both
j >= 0 and the comparison list[j] > temp, causing index errors or incorrect shifting.
- Confusing which element is placed in the sorted part (selection places the smallest; bubble places the largest).
- Stating time complexity without linking it to the presence of nested loops.
- Not showing the state of the list after each complete pass when asked for dry-run output.