Question 1

Consider a list of 10 elements:

numList = [7,11,3,10,17,23,1,4,21,5].

Display the partially sorted list after three complete passes of Bubble sort.

Accepted Answer

Bubble sort works by repeatedly swapping adjacent elements if they are in wrong order. Each pass places the next largest element at its correct position at the end.

Initial list: [7,11,3,10,17,23,1,4,21,5]

Pass 1:
Compare 7 and 11: no swap
Compare 11 and 3: swap -> [7,3,11,10,17,23,1,4,21,5]
Compare 11 and 10: swap -> [7,3,10,11,17,23,1,4,21,5]
Compare 11 and 17: no swap
Compare 17 and 23: no swap
Compare 23 and 1: swap -> [7,3,10,11,17,1,23,4,21,5]
Compare 23 and 4: swap -> [7,3,10,11,17,1,4,23,21,5]
Compare 23 and 21: swap -> [7,3,10,11,17,1,4,21,23,5]
Compare 23 and 5: swap -> [7,3,10,11,17,1,4,21,5,23]

Pass 2:
Compare 7 and 3: swap -> [3,7,10,11,17,1,4,21,5,23]
Compare 7 and 10: no swap
Compare 10 and 11: no swap
Compare 11 and 17: no swap
Compare 17 and 1: swap -> [3,7,10,11,1,17,4,21,5,23]
Compare 17 and 4: swap -> [3,7,10,11,1,4,17,21,5,23]
Compare 17 and 21: no swap
Compare 21 and 5: swap -> [3,7,10,11,1,4,17,5,21,23]

Pass 3:
Compare 3 and 7: no swap
Compare 7 and 10: no swap
Compare 10 and 11: no swap
Compare 11 and 1: swap -> [3,7,10,1,11,4,17,5,21,23]
Compare 11 and 4: swap -> [3,7,10,1,4,11,17,5,21,23]
Compare 11 and 17: no swap
Compare 17 and 5: swap -> [3,7,10,1,4,11,5,17,21,23]
Compare 17 and 21: no swap

Partially sorted list after 3 passes:
[3,7,10,1,4,11,5,17,21,23] — Bubble sort compares adjacent elements and swaps them if they are in wrong order. After each pass, the largest unsorted element moves to its correct position at the end. After 3 passes, the list partially sorted as shown.

Question 2

Identify the number of swaps required for sorting the following list using selection sort and bubble sort and identify which is the better sorting technique with respect to the number of comparisons.

List 1: 63 42 21 9

Accepted Answer

Given list: [63, 42, 21, 9]

Selection Sort:
- Pass 1: Find minimum from [63,42,21,9] is 9, swap with 63 -> [9,42,21,63] (1 swap)
- Pass 2: Find minimum from [42,21,63] is 21, swap with 42 -> [9,21,42,63] (1 swap)
- Pass 3: Find minimum from [42,63] is 42, no swap needed
Total swaps = 2

Bubble Sort:
- Pass 1:
  Compare 63 and 42: swap -> [42,63,21,9]
  Compare 63 and 21: swap -> [42,21,63,9]
  Compare 63 and 9: swap -> [42,21,9,63]
- Pass 2:
  Compare 42 and 21: swap -> [21,42,9,63]
  Compare 42 and 9: swap -> [21,9,42,63]
- Pass 3:
  Compare 21 and 9: swap -> [9,21,42,63]
Total swaps = 6

Number of comparisons:
- Selection sort: n(n-1)/2 = 6 comparisons
- Bubble sort: Worst case also about 6 comparisons

Better technique:
Selection sort has fewer swaps (2 vs 6) and same number of comparisons. Hence selection sort is better with respect to number of comparisons and swaps. — Selection sort selects minimum element and swaps once per pass, resulting in fewer swaps. Bubble sort swaps adjacent elements multiple times, resulting in more swaps. Both have similar number of comparisons.

Question 3

Consider the following lists:

List 1: 2 3 5 7 11

List 2: 11 7 5 3 2

If the lists are sorted using Insertion sort then which of the lists List1 or List 2 will make the minimum number of comparisons? Justify using diagrammatic representation.

Accepted Answer

Insertion sort works efficiently if the list is already sorted or nearly sorted.

List 1: [2,3,5,7,11] is already sorted.
Insertion sort comparisons:
- For each element, compare with previous elements until correct position found.
- Since list is sorted, each element is compared once and no shifting needed.
Total comparisons = n-1 = 4

List 2: [11,7,5,3,2] is reverse sorted.
Insertion sort comparisons:
- For each element, compare with all previous elements and shift them.
- For 7: compare with 11 (1 comparison)
- For 5: compare with 7,11 (2 comparisons)
- For 3: compare with 5,7,11 (3 comparisons)
- For 2: compare with 3,5,7,11 (4 comparisons)
Total comparisons = 1+2+3+4 = 10

Hence, List 1 makes minimum comparisons.

Diagrammatic representation:
List 1: Comparisons per element: 1,1,1,1
List 2: Comparisons per element: 1,2,3,4

Therefore, List 1 requires fewer comparisons in insertion sort. — Insertion sort is efficient for sorted or nearly sorted lists as it requires fewer comparisons and shifts. Reverse sorted lists require maximum comparisons and shifts.

Question 4

Write a program using user defined functions that accepts a List of numbers as an argument and finds its median. (Hint: Use bubble sort to sort the accepted list. If there are odd number of terms, the median is the center term. If there are even number of terms, add the two middle terms and divide by 2 get median)

Accepted Answer

Sample Python program:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

return arr

def find_median(numList):
    sorted_list = bubble_sort(numList.copy())
    n = len(sorted_list)
    if n % 2 != 0:
        median = sorted_list[n//2]
    else:
        median = (sorted_list[(n//2) - 1] + sorted_list[n//2]) / 2
    return median

# Example usage:
numList = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]
print("Median is:", find_median(numList)) — The program first sorts the list using bubble sort. Then it checks if the number of elements is odd or even. For odd, median is middle element; for even, median is average of two middle elements.

Question 5

All the branches of XYZ school conducted an aptitude test for all the students in the age group 14 - 16. There were a total of n students. The marks of n students are stored in a list. Write a program using a user defined function that accepts a list of marks as an argument and calculates the 'xth' percentile (where x is any number between 0 and 100). You are required to perform the following steps to be able to calculate the 'xth' percentile.

Note: Percentile is a measure of relative performance i.e. It is calculated based on a candidate's performance with respect to others. For example: If a candidate's score is in the 90th percentile, that means she/he scored better than 90% of people who took the test.

Steps to calculate the xth percentile:

I. Order all the values in the data set from smallest to largest using Selection Sort. In general any of the sorting methods can be used.
II. Calculate index by multiplying x percent by the total number of values, n.

For example: to find 90th percentile for 120 students:

0.90 * 120 = 108

III. Ensure that the index is a whole number by using math.round()

IV. Display the value at the index obtained in Step 3.

The corresponding value in the list is the xth percentile.

Accepted Answer

Sample Python program:

import math

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def calculate_percentile(marks_list, x):
    sorted_list = selection_sort(marks_list.copy())
    n = len(sorted_list)
    index = round((x / 100) * n)
    if index == 0:
        index = 1  # To handle 0th percentile
    if index > n:
        index = n
    return sorted_list[index - 1]  # list index starts at 0

# Example usage:
marks = [55, 70, 80, 90, 60, 75, 85]
percentile_90 = calculate_percentile(marks, 90)
print("90th percentile is:", percentile_90) — The program sorts the marks using selection sort. Then calculates the index by multiplying x% with total number of students and rounding it. The value at that index in sorted list is the xth percentile.

Question 6

During admission in a course, the names of the students are inserted in ascending order. Thus, performing the sorting operation at the time of inserting elements in a list. Identify the type of sorting technique being used and write a program using a user defined function that is invoked every time a name is input and stores the name in ascending order of names in the list.

Accepted Answer

The sorting technique used is Insertion Sort because elements are inserted in sorted order at the time of insertion.

Sample Python program:

student_names = []

def insert_name(name):
    # Insert name in ascending order
    i = 0
    while i < len(student_names) and student_names[i] < name:
        i += 1
    student_names.insert(i, name)

# Example usage:
insert_name('Ravi')
insert_name('Anita')
insert_name('Sunil')
print(student_names)  # Output: ['Anita', 'Ravi', 'Sunil'] — Insertion sort inserts each new element at its correct position in the sorted list, maintaining ascending order at all times.

Question 7

Which sorting algorithm is used to order all the values from smallest to largest when calculating the xth percentile according to the given steps?

Accepted Answer

Selection Sort — The steps to calculate the xth percentile specify ordering the data set from smallest to largest using Selection Sort, although any sorting method can be used in general.

Question 8

What does it mean if a candidate's score is in the 90th percentile?

Accepted Answer

The candidate scored better than 90% of the other candidates — Percentile is a measure of relative performance. A 90th percentile means the candidate scored better than 90% of people who took the test.

Question 9

Calculate the index to find the 75th percentile in a data set of 200 values.

Accepted Answer

150 — Given: x = 75%, n = 200
Find: Index for 75th percentile
Formula: index = math.round( (x/100) * n )
Solution: Step 1: (75/100) * 200 = 0.75 * 200 = 150
Step 2: math.round(150) = 150
Answer: 150
Note: The index must be rounded to the nearest whole number to access the correct value in the sorted list.

Question 10

Explain the role of math.round() in calculating the xth percentile index.

Accepted Answer

math.round() is used to convert the index obtained by multiplying the percentile value with the total number of data points into a whole number. For example, if the calculated index is 108.4, math.round() rounds it to 108, which is a valid index to access the sorted list. — math.round() ensures that the index used to find the xth percentile corresponds to an integer position in the sorted data set, which is necessary because list indices must be whole numbers.

Question 11

During admission, student names are inserted in ascending order as they are input. Which sorting technique does this process represent?

Accepted Answer

Insertion Sort — Inserting elements in ascending order as they arrive is characteristic of Insertion Sort, where each new element is placed in its correct position relative to already sorted elements.

Question 12

Write a user-defined function in Python that inserts a student's name into a list maintaining ascending order each time a new name is input.

Accepted Answer

a) Introduction: The function inserts a new name into an existing sorted list to maintain ascending order.
b) Function Definition:
```python
def insert_name(sorted_list, new_name):
    i = 0
    while i < len(sorted_list) and sorted_list[i] < new_name:
        i += 1
    sorted_list.insert(i, new_name)
    return sorted_list
```
c) Explanation: The function finds the correct position by comparing the new_name with existing names and inserts it at the correct index.
d) Usage: This function can be called each time a new student name is input during admission to keep the list sorted.
e) Conclusion: This approach simulates the insertion sort technique applied during data entry. — The function uses a while loop to find the correct index to insert the new name in ascending order. The insert() method places the new name at the found index, maintaining the sorted order. This approach matches the insertion sort principle of placing elements in their correct position as they arrive.

Question 13

Describe the general steps involved in calculating the xth percentile from a data set.

Accepted Answer

To calculate the xth percentile, first order all data values from smallest to largest using a sorting algorithm like Selection Sort. Then, calculate the index by multiplying x percent (x/100) with the total number of data points, n. Next, round the index to the nearest whole number using math.round(). Finally, display the value at the rounded index in the sorted list. — The process involves sorting the data to arrange it in order, determining the position corresponding to the desired percentile by calculation and rounding, and then retrieving the value at that position to represent the percentile.

Question 14

What is the main advantage of using Selection Sort for ordering data when calculating percentiles?

Accepted Answer

It requires minimal memory and is easy to implement — Selection Sort is simple to implement and requires only a small amount of additional memory, making it suitable for ordering data sets when calculating percentiles, although it is not the fastest for large data sets.

Question 15

If the total number of values in a data set is 120 and you want to find the 90th percentile, what index value will you use after rounding?

Accepted Answer

108 — Given: x = 90%, n = 120
Find: index
Formula: index = round(0.90 * 120) = round(108) = 108
Answer: 108
Note: The index corresponds to the position in the sorted data list for the 90th percentile.

Sorting

Sorting — Study Notes

Introduction

Bubble Sort

Selection Sort

Practice Questions — Sorting

All 13 Chapters in Computer Science