You have a row R of 2N coins consisting of N pennies (1C) and N dimes (10C). The

Question

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.

Explanation / Answer

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 ith odd positioned coins with last - ith coin

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

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.