Sorting — NCERT Solutions

Concept:

• Sort the list using Bubble Sort.
• If the number of elements $n$ is odd, median = element at index $n // 2$.
• If $n$ is even, median = average of elements at indices $n//2 - 1$ and $n//2$.

Program:

def bubbleSort(lst):
    n = len(lst)
    for i in range(n - 1):           # n-1 passes
        for j in range(n - 1 - i):   # compare adjacent elements
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]  # swap
    return lst

def findMedian(lst):
    sortedList = bubbleSort(lst)
    n = len(sortedList)
    if n % 2 != 0:                   # odd number of elements
        median = sortedList[n // 2]
    else:                            # even number of elements
        mid1 = sortedList[n // 2 - 1]
        mid2 = sortedList[n // 2]
        median = (mid1 + mid2) / 2
    return median

# Main program
numbers = []
 n = int(input("Enter the number of elements: "))
for i in range(n):
    num = int(input("Enter element " + str(i + 1) + ": "))
    numbers.append(num)

result = findMedian(numbers)
print("Sorted List:", numbers)
print("Median =", result)

Sample Output 1 (Odd count):

Enter the number of elements: 5
Enter element 1: 7
Enter element 2: 3
Enter element 3: 1
Enter element 4: 9
Enter element 5: 5
Sorted List: [1, 3, 5, 7, 9]
Median = 5

Sample Output 2 (Even count):

Enter the number of elements: 4
Enter element 1: 4
Enter element 2: 2
Enter element 3: 8
Enter element 4: 6
Sorted List: [2, 4, 6, 8]
Median = 5.0

Explanation:

• bubbleSort() sorts the list in ascending order using nested loops.
• findMedian() checks if $n$ is odd or even and returns the appropriate median value.

Concept:

• Sort the marks list using Selection Sort.
• Calculate index = $\text{round}\left(\dfrac{x}{100} \times n\right)$
• The value at that index in the sorted list is the $x^{th}$ percentile.

Program:

import math

def selectionSort(lst):
    n = len(lst)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        # Swap the found minimum with the first element of unsorted part
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

def calculatePercentile(marks, x):
    # Step I: Sort the list using Selection Sort
    sortedMarks = selectionSort(marks)
    n = len(sortedMarks)
    
    # Step II: Calculate index
    index = (x / 100) * n
    
    # Step III: Round to whole number
    index = math.ceil(index)   # using ceil to get the next whole number
    
    # Ensure index is within valid range
    if index >= n:
        index = n - 1
    
    # Step IV: Display the value at that index
    print("Sorted Marks:", sortedMarks)
    print("Index calculated:", index)
    print("The", x, "th percentile value is:", sortedMarks[index])

# Main program
marks = []
n = int(input("Enter the number of students: "))
for i in range(n):
    m = int(input("Enter marks of student " + str(i + 1) + ": "))
    marks.append(m)

x = int(input("Enter the percentile to calculate (0-100): "))
calculatePercentile(marks, x)

Sample Output:

Enter the number of students: 5
Enter marks of student 1: 45
Enter marks of student 2: 78
Enter marks of student 3: 62
Enter marks of student 4: 90
Enter marks of student 5: 55
Enter the percentile to calculate (0-100): 90
Sorted Marks: [45, 55, 62, 78, 90]
Index calculated: 5
The 90 th percentile value is: 90

Explanation:

• selectionSort() sorts the marks in ascending order.
• Index = $\text{round}(0.90 \times 5) = \text{round}(4.5) = 5$, but since valid indices are 0–4, we use index 4 (last element).
• The value at that index is the $x^{th}$ percentile.

Identification of Sorting Technique:

The sorting technique being used here is Insertion Sort. In Insertion Sort, each new element is inserted at its correct position in the already-sorted portion of the list. Similarly, here, every time a new name is entered, it is inserted at the correct position in the already-sorted list of names.

Concept: Maintain a sorted list. When a new name is inserted, compare it with existing names from the end of the list and shift names that are greater than the new name one position to the right, then insert the new name at the correct position.

Program:

def insertName(nameList, newName):
    """
    Inserts newName into nameList at the correct
    position to maintain ascending (alphabetical) order.
    """
    # If list is empty, simply append
    if len(nameList) == 0:
        nameList.append(newName)
        return nameList
    
    # Find the correct position using Insertion Sort logic
    i = len(nameList) - 1
    nameList.append(None)   # Extend list by one position
    
    while i >= 0 and nameList[i] > newName:
        nameList[i + 1] = nameList[i]   # Shift element to the right
        i -= 1
    
    nameList[i + 1] = newName           # Insert at correct position
    return nameList

# Main program
studentNames = []
n = int(input("Enter the number of students: "))

for i in range(n):
    name = input("Enter name of student " + str(i + 1) + ": ")
    studentNames = insertName(studentNames, name)
    print("Current sorted list:", studentNames)

print("\nFinal sorted list of student names:")
for name in studentNames:
    print(name)

Sample Output:

Enter the number of students: 5
Enter name of student 1: Riya
Current sorted list: ['Riya']
Enter name of student 2: Amit
Current sorted list: ['Amit', 'Riya']
Enter name of student 3: Zara
Current sorted list: ['Amit', 'Riya', 'Zara']
Enter name of student 4: Meena
Current sorted list: ['Amit', 'Meena', 'Riya', 'Zara']
Enter name of student 5: Kiran
Current sorted list: ['Amit', 'Kiran', 'Meena', 'Riya', 'Zara']

Final sorted list of student names:
Amit
Kiran
Meena
Riya
Zara

Explanation:

• The function insertName() is called every time a new name is entered.
• It shifts all names that are alphabetically greater than the new name one position to the right.
• The new name is then placed at the correct position, maintaining ascending alphabetical order at all times.
• This is exactly how Insertion Sort works — inserting each element at its proper place in the sorted portion.