Q.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.

def insert_name(names, new_name):
    '''Insert new_name into the already-sorted list 'names'.'''
    names.append(new_name)                  # make room at the end
    i = len(names) - 2
    while i >= 0 and names[i].lower() > new_name.lower():
        names[i + 1] = names[i]             # shift the bigger name right
        i -= 1
    names[i + 1] = new_name                 # drop it into the gap
    return names

students = []
for name in ['Rahul', 'Anita', 'Zoya', 'Meera']:
    insert_name(students, name)
    print('After inserting', name, ':', students)

Output

After inserting Rahul : ['Rahul']
After inserting Anita : ['Anita', 'Rahul']
After inserting Zoya : ['Anita', 'Rahul', 'Zoya']
After inserting Meera : ['Anita', 'Meera', 'Rahul', 'Zoya']
``` …

Concept understanding — identifying the technique

Look at what the admission office actually does:

• The names already in the register are sorted.
• A new student arrives, and that one name has to find its place among them.
• Nothing else moves out of order; only the names bigger than the newcomer slide one step right.

That is the definition of insertion sort: maintain a sorted prefix, and insert the next element into it. It is the only one of the elementary sorts that is incremental — it can sort data that is still arriving, which is exactly the situation here. Bubble sort and selection sort both need the whole list in hand before they can start.

Algorithm — inserting one name

1. Append the new name at the end of the list (this reserves a slot).
2. Set i to the index of the last old name.
3. While i >= 0 and names[i] is alphabetically greater than the new name: a. Copy names[i] one position to the right. b. Decrease i by 1.
4. Write the new name at names[i + 1] — the gap left behind.

Comparing with .lower() makes the ordering case-insensitive, so anita and Anita sort alike.

Program

def insert_name(names, new_name):
    '''Insert new_name into 'names', keeping it sorted in ascending order.'''
    names.append(new_name)                       # step 1 - reserve a slot
    i = len(names) - 2                           # step 2 - last old index

    while i >= 0 and names[i].lower() > new_name.lower():
        names[i + 1] = names[i]                  # step 3a - shift right
        i -= 1                                   # step 3b

    names[i + 1] = new_name                      # step 4 - place it
    return names


# ---- driver: called every time a name is input ----
students = []
n = int(input('How many admissions? '))
for k in range(n):
    name = input('Enter name of student: ')
    insert_name(students, name)
    print('Register now:', students)

print('\nFinal admission list (ascending):', students)

Sample run (input names: Rahul, Anita, Zoya, Meera)

How many admissions? 4
Enter name of student: Rahul
Register now: ['Rahul']
Enter name of student: Anita
Register now: ['Anita', 'Rahul']
Enter name of student: Zoya
Register now: ['Anita', 'Rahul', 'Zoya']
Enter name of student: Meera
Register now: ['Anita', 'Meera', 'Rahul', 'Zoya']

Final admission list (ascending): ['Anita', 'Meera', 'Rahul', 'Zoya']

Dry run of the insertion of Meera

List before this call: ['Anita', 'Rahul', 'Zoya']. After append, the working list is ['Anita', 'Rahul', 'Zoya', 'Meera'] and i = 2.