XI SORTING ALGORITHM ASSIGNMENT TYPE-B SOLUTION

1. Find the number of operations:(a) seq is a list having some numbers

for i in range(1,len(seq)):
    key = seq(i)
    # invariant: seq[:i] is sorted
    # find the least ‘low’ such that seq[low] is not less than key
    low, up = 0, i
    while up > low:
        middle = (low+up) //2
        if seq[middle] < key:
            low = middle+1
        else
            up = middle
        # insert key at position low
        seq[:] = seq[:low]+[key]+seq[low:i] + seq[i+1:]

Sol: let the sequence is n, then  line 1,2,3 will execute a total of n-1 times from 1 to n-1. Therefore \(ops = 3(n-1)\). For While loop, sum of low and up is divided by 2, So, it will run once for the first two times (for loops), twice the next four times. Thrice the next eight times and so on. If \(n=14\), the while loop has ops line 4,5,9 and 7 and 8. So it runs 5 times the first two times, ten times the next 4 times, 15 times the next 7 times. Hence \( ops = 3*(14-1)+2*5+4*10+7*15 = 194 \)
Remember the sample list (seq) must be already sorted.

(b) Let len(values) be n

length = len(values)
 	for time in range(0, length-1):
        for position in range(0, length-time-1)):
            if values[position] > values[position+1]:
                temp = values[position]
                values[position] = values[position+1]
                values[position+1] = temp

Sol: line 1 is one operation. The outer for loop will run n-1 times. The inner for loop will run n-1 times first then n-2 times and so on. It has 1 comparison and 3 assignments. \(Total Ops = 1+n-1+4*[(n-1)+(n-2)…1] = (n+2)(n-1)/2+1\)

(c) steps = 0

length = len( values )
for time in range(0,length-1):
    for position in range(0, (length-time-1)):
        if values[position] > values[position+1]:
            temp = values[position]
            values[position] = values[position+1]
            values[position+1] = temp
            steps = steps+1
    if steps>10:
        break
print("steps taken to sort the list:", steps)

Sol: There will be no steps taken to sort the list because the code breaks once the steps become greater than 10.

2. Find out the number of operations taking place in the codes given below. Both codes are 90% similar. Thus carefully determine the number of operations in each of these.

(a)

twoMult = 0
threeMult = 0
n = int(input("Enter N:"))
while n > 0:
    r = n% 2
    if r == 0:
        twoMult = twoMult + n
    else:
        r = n % 3
    if r == 0:
        threeMult = threeMult + n
    n= int(input("Enter n: "))
    print(twoMult, threeMult)

Sol: Line-1, 2 & 3 are one operations each. The while loop will keep asking for input and will run until the input given is positive. : line-5 is one op. Line-6 is a comparison, if its true, there will be one more op else 2 if (line-10) is false else 3, Line-11 will be one op and finally outside the loop line-12 will be one op. Operations from line-4  to 9 will run until input is given positive. So the total \(ops = 3+ \ number \ of  \ +ve \ inputs* [2+(1 or 2 or 3) + 1]+1\)

(b) See the code below

twoMult = 0
threeMult = 0
N = int(input("Enter N: "))
while N>0 :
    R = N%2
    if R==0:
        twoMult = twoMult + N
        continue
    else:
        R = N % 3
        if R==0:
            threeMult = threeMult + N
            break
    N = int(input("Enter N: "))
print(twoMult, threeMult)

Sol: Both (a) and (b) are the same except that we have the continue with the latter. The continue statement in (b) runs the next iteration while the break statement breaks the loop in (a). As a result, there will be an equal number of operations for both (a) and (b) up until one of the two propositions is true. No adjustment in the number of operations will be made before that.

3. Take a list of 8 numbers and sort it using both bubble sort and insertion sort. Then find out the difference in number of operations taking place in both these sorting techniques.

Sol: See the code for both algorithm below:

import random
def insertion_sort(arr):
    ops =0
    for I in range(1, len(arr)):
        key = arr[i]
        j = i-1
        ops +=3
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            ops += 3
        arr[j+1] = key
        ops +=1
    return ops
def bubble_sort(arr):
    ops = 0
    for i in range(len(arr)-1):
        ops += 1
        for j in range(i+1, len(arr)):
            ops +=2
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
                ops +=1
    return ops

(a) Generate a list of 8 numbers within the range of 50 and print the outputs of both algorithm

lst= random.sample(range(50),8) # this will generates a list of random numbers
print('No. of ops in insertion sort is: ', insertion_sort(lst))
print('No. of ops in bubble sort is :', bubble_sort(lst))

(b) Generate a list of 80 numbers within the range of 50 and print the outputs of both algorithm.

lst= random.sample(range(50),80) # this will generates a list of random numbers 
print('No. of ops in insertion sort is: ', insertion_sort(lst)) 
print('No. of ops in bubble sort is :', bubble_sort(lst))

From the random outputs generated from both algorithm, we can conclude that as the size increases, insertion sort is more effective than bubble sort since it does fewer comparisons and swaps than bubble sort.

Note: We count each line as one operation in accordance with the sample provided in our textbook. The real number of operations may be different and larger.