CLASS-XI SORTING ALGORITHM ASSIGNMENT TYPE-C SOLUTION

1. Election is a dictionary where key:value pairs are in the form of name:votes received. Write a program that sorts the contents of the Election dictionary and creates two lists that stores the sorted data. List A[i] will contain the name of the candidate and ListB[i] will contain the votes received by candidate ListA[i]. Print the name of candidates with votes received in descending order of the number of votes received.

Sol:

def bubble_sort(arr):
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[i][1] < arr[j][1]:
                arr[i], arr[j] = arr[j], arr[i]
    return arr
electiondic = {'Rinhlua':500, 'Rama':395, 'Zira':800, 'Avana':1000, 'Muana':900}
etuple = bubble_sort(list(electiondic.items()))

A1 = [etuple[i][0] for i in range(len(etuple))] # list of names
B1 = [etuple[i][1] for i in range(len(etuple))] # list of votes
for i in range(len(etuple)):
    print(A1[i], B1[i])

Output:

Avana 1000
Muana 900
Zira 800
Rinhlua 500
Rama 395

Note: electiondic .items() returns a list of tuples with each tuple being key:value pair from the election dictionary.

2. Given following list L that stores the names of Nobel prize winners . Each element of the list is a tuple containing details of one Nobel prize winner.

L = [ ("Wilhelm Conrad R’ontgen", "Physics", 1901), ("Ronald Ross", "Medicine", 1902), ("Marie Curie", "Physics", 1903) ("Ivan Pavlov", "Medicine", 1904), ("Henryk Sienkiewicz", "Literature", 1905), ("Theodore Roosevelt", "Peace", 1906)]

Write a program to sort the list in the order of Last names of the winners. Use insertion sort algorithm.

Sol:

def insertion_sort(arr):
    for i in range(1,len(arr)):
        key = arr[i]
        # split() is used for splitting the names using spaces and then [-1] is used to capture the last name
        k = arr[i][0].split()[-1]
        j = i-1
        while j >= 0 and k < arr[j][0].split()[-1]:
            arr[j+1] = arr[j]
            j -= 1
            arr[j+1] = key
    return arr

L = [("Wilhelm Conrad R'ontgen", "Physics", 1901), ("Ronald Ross", "Medicine", 1902),
("Marie Curie", "Physics", 1903), ("Ivan Pavlov", "Medicine", 1904),
("Henryk Sienkiewicz", "Literature", 1905), ("Theodore Roosevelt", "Peace", 1906)]
print(insertion_sort(L))

Output: 

[('Marie Curie', 'Physics', 1903),
('Ivan Pavlov', 'Medicine', 1904),
("Wilhelm Conrad R'ontgen", 'Physics', 1901),
('Theodore Roosevelt', 'Peace', 1906),
('Ronald Ross', 'Medicine', 1902), (
'Henryk Sienkiewicz', 'Literature', 1905)]

3. Write a program to read a list containing 3-digit integers only. Then write an insertion sort program that sorts the list on the basis of one’s digit of all elements. That is, if given list is:

Sol: [128, 256, 512, 124] then the sorted list (as per above condition) should be [512, 124, 256, 128]. Here we take the last digit of each element and sort it.

Code:

def insertion_sort(arr):
    for i in range(1,len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key[-1] < arr[j][-1]: # [-1] is used to take the last digit
            arr[j+1] = arr[j]
            j -= 1
            arr[j+1] = key
    return arr
lst = input("Enter a list of 3 digit nos: ").split()
print(insertion_sort(lst))

Note: split() divides the input on whitespace; we are not doing an int type conversion to get the last digit here. Make sure you put whitespace between each element when running the code.

4. Write a program to perform sorting on a given list of strings, on the basis of length of strings. That is, the smallest-length string should be the first string in the list and the largest-length string should be the last string in the sorted list.

Sol:

def insertion_sort(arr):
    for i in range(1,len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and len(key) < len(arr[j]): # comparison on the basis of length
            arr[j+1] = arr[j]
            j -= 1
            arr[j+1] = key
    return arr

l = input("Enter a list of strings : ").split() # split() splits the input on whitespace
print(insertion_sort(l))

Output:

 

 

5. Write a program that sorts a list of tuple-elements in descending order of Points using Bubble sort.

The tuple elements of the list contain following information about difference players:
(PlayerNo, Playername, Points)
Sample content of the list before sorting:

[(103, Ritika, 3001),(104, John, 2819),(101, Razia, 3451),(105, Tarandeep, 2971)]

After sorting the list would be like:

[(101,Razia,3451),(103, Ritika,3001),(105,Tarandeep, 2971), (104, John, 2819)]

Sol:

def bubble_sort(arr):
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[i][2] < arr[j][2]:  #arr[j][2] is points
                arr[i], arr[j] = arr[j], arr[i]
    return arr
lst = [(100,'Nundika',3450),(103,'Rinhlua',3001), (104,'Buatsaiha',2819),(101,'Zara', 3451), (105,'Lawmawmi',2971),(106,'Amuani',3500)]
print(bubble_sort(lst))

Note: All the solutions are tested in python 3.8.9.