Answer to Question #216715 in Java | JSP | JSF for Anonymous

Question

Consider a pile of coins. You have given ‘n’ coins of different sizes and you want to sort the pile so that smaller coins are on the top of larger ones. The only “operation” you are allowed to perform is- take top ‘k’ coins together, and place them back to the pile upside down.

1. Describe an algorithm to sort an arbitrary pile of n coins using O(n) operations. Exactly how many operations does your algorithm perform in the worst case.
2. For every positive integer ‘n’, describe the pile structure that requires (Omega) Ω(n) operations to sort. In other words, generate an example of a pile that will require at least cn operations for some c > 0. (n > 3)
3. Now suppose in the sorted array we want all coins to have heads face up. Describe an algorithm to sort an arbitrary pile of ‘n’ coins, such that all coins have tails face down, using O(n) operations. Exactly how many operations does your algorithm perform in the worst case.

Answer 1

import java.io.*;
 
class PileCoins {
    static void flip(int arr[], int i)
    {
        int temp, start = 0;
        while (start < i)
        {
            temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
            start++;
            i--;
        }
    }
 
    static int getMax(int arr[], int n)
    {
        int x, i;
        for (x = 0, i = 0; i < n; ++i)
            if (arr[i] > arr[x])
                x = i;
        return x;
    }
    static int coinSort(int arr[], int n)
        for (int c = n; c > 1; c--)
        {
            int x = getMax(arr, c);
            if (x != c-1)
            {
                flip(arr, x);
                flip(arr, c-1);
            }
        }
        return 0;
    }
 
    static void printArray(int arr[], int size)
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
        System.out.println("");
    }
 
    public static void main (String[] args)
    {
        int arr[] = {1,2,3,4,5,6};
        int n = arr.length;
         
        coinSort(arr, n);
         
        System.out.println("Sorted Array: ");
        printArray(arr, n);
    }
}
	public static void main(String[] args) {
		System.out.println("Hello World");
	}
}