Sorting

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.

Answer

numList = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]
n = len(numList)
for i in range(3):
    for j in range(0, n - i - 1):
        if numList[j] > numList[j + 1]:
            numList[j], numList[j + 1] = numList[j + 1], numList[j]
print("Partially sorted list after three passes of Bubble sort:")
print(numList)

Partially sorted list after three passes of Bubble sort:
[3, 7, 10, 1, 4, 11, 5, 17, 21, 23]

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 :

Answer

Selection Sort

Bubble Sort

As we can see from the diagrammatic representation above, selection sort performs 2 swaps whereas bubble sort performs 6 swaps. Hence, selection sort is a better sorting technique with respect to the number of comparisons.

Consider the following lists:

List 1:

List 2:

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

Answer

Diagrammatic representation of the sorting of List 1 and List 2 using Insertion sort is shown below:

From the diagrams, we can clearly see that List 1 requires no swaps, while List 2 requires multiple (10) swaps during the insertion sort process. Therefore, List 1 makes the minimum number of comparisons and swaps when sorted using insertion sort.

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)

Answer

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

def find_median(arr):
    n = len(arr)
    bubble_sort(arr)  

    if n % 2 == 0:  
        mid1 = arr[n // 2 - 1]
        mid2 = arr[n // 2]
        median = (mid1 + mid2) / 2
    else: 
        median = arr[n // 2]

    return median

numbers = eval(input("Enter a list of numbers: "))
median = find_median(numbers)
print("Median of the list is:", median)

Enter a list of numbers: [20, 2, 31, 4, 10]
Median of the list is: 10

Enter a list of numbers: [22, 11, 16, 7, 8, 12]
Median of the list is: 11.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:

1. 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.
2. 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.
3. Ensure that the index is a whole number by using math.round().
4. Display the value at the index obtained in Step 3.

The corresponding value in the list is the x^th percentile.

Answer

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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]

def calculate_percentile(marks_list, percentile):
    selection_sort(marks_list)
    n = len(marks_list)
    index = round(percentile * n / 100) - 1 
    if index >= 0 and index < n:
        return marks_list[index]
    else:
        return None  
    
marks = eval(input("Enter list of marks"))
xth_percentile = int(input("Enter percentile to be calculated: "))
result = calculate_percentile(marks, xth_percentile)

if result is not None:
    print("The", xth_percentile, "th percentile is:", result)
else:
    print("Invalid percentile.")

Enter list of marks[35, 25, 45, 50, 60, 75, 80]
Enter percentile to be calculated: 70
The 70 th percentile is: 60

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.

Answer

The sorting technique being used in the program is Insertion Sort. In Insertion Sort, elements are sorted by inserting each element into its correct position in the sorted part of the list.

def insert_name(names_list, new_name):
    index = len(names_list)
    for i in range(index):
        if new_name < names_list[i]:
            index = i
            break
    names_list.insert(index, new_name)

names_list = []

while True:
    new_name = input("Enter a name (or 'exit' to stop): ")
    if new_name.lower() == 'exit':
        break
    insert_name(names_list, new_name)

print("Sorted list of names:")
for name in names_list:
    print(name)

Enter a name (or 'exit' to stop): Amruth
Enter a name (or 'exit' to stop): Parth
Enter a name (or 'exit' to stop): Sanket
Enter a name (or 'exit' to stop): Shrestha
Enter a name (or 'exit' to stop): Nikita
Enter a name (or 'exit' to stop): exit
Sorted list of names:
Amruth
Nikita
Parth
Sanket
Shrestha