You have a row R of 2N coins consisting of N pennies 1C and

You have a row R of 2N coins consisting of N pennies (1C) and N dimes (10C). They alternate as follows: (1C) (10C) (1C) (10C)... and so on. Design a sorting (pseudocode) algorithm to sort these coins from smallest to largest value. The only moves you are allowed to make are those that interchange the positions of two neighboring coins. You may use array notation in your pseudocode (i.e. R[0] refers to the first position, R[1] is the second position, etc.). As an example, the sorted version for N=3 will look like the following: (1C) (10C) (1C) (10C) (1C) (10C) rightarrow (1C) (1C) (1C) (10C) (10C) (10C) Analyze your function in O-notation (function class only). Once again, a portion of your mark will be based on the efficiency of your algorithm.

Solution

Hi, I am attaching a python3 code to test the algorithm:

l=[]
n=int(input(\"Enter the value of 2N: \"))
for i in range(n):
if(i%2==0):
l.append(1)
else:
l.append(10)

print(\"Unsorted data:\")
for i in range(n):
print(l[i])

def sort(l,n):
for i in range(int(n/2)):
#swap
if(i%2==1):
temp=l[i]
l[i]=l[n-i-1]
l[n-i-1]=temp
sort(l,n)

print(\"Sorted data: \")
for i in range(n):
print(l[i])

Algo:

for half of the coins (ie n)

swap i^th odd positioned coins with last - i^th coin

Running time: for 2n coins, running time will be O(n)