Task: You have a row R of 2N coins consisting of N pennies (1C) and N dimes (10c

Question

Task: You have a row R of 2N coins consisting of N pennies (1C) and N dimes (10c). They alternate as follows: (1) (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) (10(100(10(10C)-) (10(10(10(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

Algorithm sortDimesCents

Input:

N

print N cents followed by N Dimes with an array of Size 2N.

Complexity: O(N) - Only for loop executing O(1) statement that is the print statement.

Logic is to count the number of Cents and no of Dimes to print them first in sorted order like once printing of cents is done then printing of Dimes is completed. For this we need to know only value of n. as in 2N coins alternating cents and dimes means we have equal number of cents and dimes and no of cents will be equal to n while number of dimes will also be n.

Code Snippet in C:

#include <stdio.h>

#define MAX 100

int main(void) {

     int n, count;

     printf(" Enter N:");

     scanf(" %d", &n);

     for(count = 0; count < n; count++)

          printf(" 1C");

    for(;count < 2*n;count++)

        printf(" 10C");

return 0;

}

Output :

Enter N : 3

1C 1C 1C 10C 10C 10C

The logic is that, Suppose you need to sort an array of 0's and 1's then you need not use a regular sorting algorithm. Instead you could just count number of 0's and number of 1's and then print the array with counted number of 0's followed by number of 1's identified in the input array.

Here in this particualar problem, cents and dimes are alternating, and it is also given that 2N coins are there. If 2N coins are there and 2 types of coins are alternating, then each coin type will be N in number in the row. Based on this logic, first we printed the row with N cents, and then followed by N Dimes. Any other sorting agorithm would take more time complexity as they would involve nested for loops (O(n^2)) or O(nlogn) even in case of merge sort. But O(n) is a better time complexity for this problem.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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