UVA Problem 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Given 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We are to calculate the number of ways the input amount can be distributed with this coins.

This problem is a bit harder. It can be solved with dynamic programming or using greedy technique. Use bottom up technique instead of top down to speed it up.

We can also replace this,

 for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

with this since we know no matter what the input it is always possible to give 1 cents,

for(j = 0; j < N; ++j)
        a[j] = 1;

It is hard to visualize without drawing the recursion tree or the array. The first 20 indexes of the array looks like this,

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Coins: 1 1 1 1 1 2 2 2 2 2 4  4  4  4  4  6  6  6  6  6  9

Explanation:

/* TO DO */

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

11
26
5
4

Output:

4
13
2
1

Code Bottom Up:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>
#define N 8000

static int a[N] = {1, 1, 1, 1, 1};
static const int coins[4] = {5, 10, 25, 50};

int main()
{
    register int i, j;

    for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

    for(i = 0; i < 4; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[ j - coins[i] ];
    }

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

    return 0;
}

Loop Fission Variant:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>

#define N 8000
#define M 5

static int a[N] = {1, 1, 1, 1, 1};

int main()
{
    register int i, j;

    for(j = M; j < N; ++j)
        a[j] += a[j - 1];

    for(j = 5; j < N; ++j)
        a[j] += a[j - 5];

    for(j = 10; j < N; ++j)
        a[j] += a[j - 10];

    for(j = 25; j < N; ++j)
        a[j] += a[j - 25];

    for(j = 50; j < N; ++j)
        a[j] += a[j - 50];

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

    return 0;
}

UVA Problem 10327 – Flip Sort Solution

UVA Problem 10327 – Flip Sort Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Another sorting problem that requires us to “exchange two adjacent terms”. Use any stable sort to count the number of swaps. That is the output.

Here among three code the first one is a hybrid distribution between insertion sort and merge sort to count inversions / swaps. The next two codes are merge sort and bubble sort.

This merge sort also be made to work with selection sort. Please see Introduction to Algorithms book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein for more detail.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

3
1 2 3
3
2 3 1

Output:

Minimum exchange operations : 0
Minimum exchange operations : 2

Hybrid Merge Sort and Insertion Sort Distribution:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

#define INSERTION_SORT_THERSHOLD 20

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid - front + 1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void insertionSort(int front, int rear) {
    register int i, j;
    int key;

    for (i = front + 1; i <= rear; ++i) {
        key = A[i];
        j = i - 1;
        while (j >= front && A[j] > key) {
            A[j + 1] = A[j];
            ++c;
            --j;
        }
        A[j + 1] = key;
    }
}

/**
 * Hybrid distribution between insertion sort and merge sort
 * Performs slower than regular merge sort for this small input range
 * Such distribution also works with selection sort
 * Please refer to book introduction to algorithm for more
 */
void HybridMergesort(int front, int rear){
    if(rear - front < INSERTION_SORT_THERSHOLD)
        insertionSort(front, rear);
    if(front < rear){
       int mid = (rear + front) >> 1;
       HybridMergesort(front, mid);
       HybridMergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);

        HybridMergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Merge Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);
        Mergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Bubble Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<cstdio>
#include<iostream>

static unsigned a[1024];

int main(){
    register unsigned int i, j, k, n;
	while(scanf("%u", &n) == 1){
        for(i = 0; i < n; ++i)
            scanf("%u", &a[i]);

        /**
         * Bubble Sort
         */
        for(k = j = 0; j < n; ++j){
            for(i = 0; i < n - j - 1; ++i){
                if(a[i] > a[i + 1]){
                    std::swap(a[i], a[i + 1]);
                    ++k;
                }
            }
        }

        printf("Minimum exchange operations : %u\n", k);
	}
	return 0;
}

Insertion Sort Best Case Time Complexity Analysis

Insertion Sort Best Case Time Complexity Analysis:

Insertion Sort Code:

for (/*c1*/ i = 1; /*c2*/ i < n; /*c3*/ ++i){
     /*c4*/ key = A[i];
     /*c5*/ j = i - 1;
     /*c6*/ while (j >= 0 && key < A[j]){
        /*c7*/ A[j+1] = A[j];
        /*c8*/ --j;
    }
    /*c9*/ A[j+1] = key;
}

Analysis:

Let, c1, c2, c3… be micro instructions for a particular command. Let input size, n = 6. Now setting n = 6 in the code above we find this relation below.

Micro Instructions    Times (Number of times it was executed)
==================    =======================================
              c1 -----> 1
              c2 -----> 6 -----> ( n )
              c3 -----> 5 -----> ( n - 1 )
              c4 -----> 5 -----> ( n - 1 )
              c5 -----> 5 -----> ( n - 1 )
              c6 -----> 5 -----> ( n - 1 )
              c7 -----> 0
              c8 -----> 0
              c9 -----> 5 -----> ( n - 1 )

Explanation:

Our input instance size was 6. Here (c1) always executes only once. But the for loop condition (c3) executes 6 times since our for loop counter is initialized to 1 instead of 0.

For 1 its checks condition once. Finds 1 < 6 true continues loop.
For 2 its checks condition once. Finds 2 < 6 true continues loop.
For 3 its checks condition once. Finds 3 < 6 true continues loop.
For 4 its checks condition once. Finds 4 < 6 true continues loop.
For 5 its checks condition once. Finds 5 < 6 true continues loop.
For 6 its checks condition once. Finds 6 < 6 false exits the loop.

Since the loop counter begins at 1 so condition is checked from 1 to n times. For the nth time even though it results in false but condition is executed to get that false result. The loop condition (c2) is checked 6 times (n) but it enters the loop 5 times (n-1). So for this algorithm if the input size is (n) the condition will be checked (n) times. The last check 6 < 6 is false. So it breaks the loop.

Inside the loop in any case (c4, c5, c6, c9) is always executed in the best case. But in the event of best case the while loop condition becomes false. So instructions inside while loop ( c7, c8 ) are never executed. For this reason we have a faster runtime.

For insertion sort the best case is input is already sorted in the desired order. So it never enters the while loop since key is never less/greater ( depending on ascending or descending order sort ) than its previous elements.

The loop increment is executed (n – 1) times because when it enters the loop for the first time the increment is not executed.


So we can write,

T(n) = summation of micro instructions * number of times executed

T(6) = c1 + n*c2 + (n-1)*c3 + (n-1)*c4 + (n-1)*c5 + (n-1)*c6 + 0*c7 + 0*c8 + (n-1)*c9

     = (c1 - c2 - c3 - c4 - c5 - c6 - c9) + n * (c2 + c3 + c4 +c5 + c6 + c9)  [multiplying and rearranging constants]

     = b + n * a  [ Let, sum of constants, c1 - c2 - c3 - c4 - c5 - c6 - c9 = b, c2 + c3 + c4 +c5 + c6 + c9 = a ]

     = an + b

     = Ω(n)

Lower Bound,

We represent asymptotic lower bounds with big – Ω ( Big Omega ) notation. So the lower bound for insertion sort is Big Omega of n.

Ω(n)


Now,

T(n) = an + b

we know,
y = mx + c
f(x) = mx + c

From this we can see these equations are similar and our equation matches linear equation. If we plot the graph of an+b for different values of n we will see that it is a straight line. So for any value of n it will give us linear time. Even as input size gets very large our time complexity will always be linear. So, we can write this as Ω(n). Also known as Big Omega.

Machine Independent Worst Case Time Complexity Analysis Linear Search

Machine Independent Worst Case Time Complexity Analysis Linear Search:

Linear Search C Code:

/*c1*/ found = 0;

/**
 * What if the input size was (n) instead of 6
 */
for (/*c2*/ i = 0; /*c3*/ i < 6; /*c7*/ ++i){
     /*c4*/     if (A[i] == key){
     /*c5*/         found = i;
     /*c6*/          break;
                }
}

/*c8 */ if (found)
/*c9 */    printf("Found at %d\n", i);
/*c10*/ else
           printf("Not found");

Analysis:

Let, c1, c2, c3… be micro instructions for a particular command. Let input size, n = 6.

Micro Instructions    Times (Number of times it was executed)
==================    =======================================
              c1 -----> 1
              c2 -----> 1
              c3 -----> 7 -----> ( n + 1 )
              c4 -----> 6 -----> ( n )
              c5 -----> 6 -----> ( n )
              c6 -----> 6 -----> ( n )
              c7 -----> 6 -----> ( n )
              c8 -----> 1
              c9 -----> 1
             c10 -----> 0

Explanation:

Our input instance size was 6. Here (c1) always executes only once. So does (c2) when initializing the for loop condition. But the for loop condition (c3) executes 7 times. Our for loop counter is initialized to 0.

For 0 its checks condition once. Finds 0 < 6 true continues loop.
For 1 its checks condition once. Finds 1 < 6 true continues loop.
For 2 its checks condition once. Finds 2 < 6 true continues loop.
For 3 its checks condition once. Finds 3 < 6 true continues loop.
For 4 its checks condition once. Finds 4 < 6 true continues loop.
For 5 its checks condition once. Finds 5 < 6 true continues loop.
For 6 its checks condition once. Finds 6 < 6 false exits the loop.

The loop condition (c3) is checked 7 times (n+1) but it enters the loop 6 times (n). So for this algorithm if the input size is (n) the condition will be checked (n+1) times. The last check 6 < 6 is false. So it doesn’t enter the loop.

Inside the loop in any case (c4) is always executed. In the event of worst case (c4) is true every time (n), then two more micro instructions are executed (c5), (c6).

The loop increment is executed (n) times because when it enters the loop for the first time the increment is not executed.

(C8) is always executed once. Then based on the truth value of (c8) either (c9) or (c10) is executed once.


So we can write,

T(n) = summation of micro instructions * number of times executed

T(6) = 1*c1 + 1*c2 + 7*c3 + 6*c4 + 6*c5 + 6*c6 + 6*c7 + 1*c8 + 1*c9 + 0*c10

     = c1 + c2 + c3 + 7*c3 + 6*c4 + 6*c5 + 6*c6 + 6*c7 + c8 + c9

     = c1 + c2 + c3 + (n+1)*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9   [substituting 6 with n]

     = c1 + c2 + c3 + c3 + n*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9

     = c1 + c2 + c3 + c3 + n*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9  [rearranging constants]

     = ( c1 + c2 + 2*c3 + c8 + c9 ) + n * ( c3 + c4 + c5 + c6 + c7 )

     = b + n * a  [ Let, sum of constants, c1 + c2 + 2*c3 + c8 + c9 = b, c3 + c4 + c5 + c6 + c7 = a ]

     = an + b

     = O(n)

Now,

T(n) = an + b

we know,
y = mx + c
f(x) = mx + c

From this we can see these equations are similar and our equation matches linear equation. If we plot the graph of an+b for different values of n we will see that it is a straight line. So for any value of n it will give us linear time. Even as input size gets very large our time complexity will always be linear. So, we can write this as O(n). Also known as order, Big O.

UVA Problem 11462 – Age Sort Solution

UVA Problem 11462 – Age Sort Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

First of all a warning. This is going to be a very very very long post. For this problem i will use various divide and conquer algorithms ( Ex: quick sort, merge sort etc ) & techniques to solve.

The best Solution here takes 0.502 s ( 502 ms ) . If you are looking for a very fast solution this is not the right place. But these code can be optimized to create a very fast solution.  Also sorts such as bubble sort, selection sort, insertion sort, replacement sort won’t be able to sort in time. So you’ll get TLE if you use these sort.

Lets begin:

This is a sorting problem. The only trouble here is the huge count of test cases. But there’s very important line most miss including me. That is ” no individual in that country lives for 100 or more years “. So we may have many many test cases but no input age is more than 100. 🙂

Now lets look at our solution menu,

1. Counting sort ( Just count occurrence of each values, then print them 0 to 100 for ascending order).

2. Binary Merge sort ( 2 partition ).

3. Ternary Merge sort ( 3 partition ).

4. Quick sort ( 2 partition ).

5. Quick sort ( 3 partition ).


The first solution code here ( counting sort ) runs the fastest since it just count elements at each index and prints them. This solution may be made faster by using combination of fread, fwrite, strtok, atoi, stringstream ( <sstream> ) . Although i haven’t used them. If i get time I will try to implement them in future.

I used the other sorts here just demonstrate implementation of merge sort and quick sort algorithms. I may include more sorting algorithms for this problem in future. All codes are well commented take a look below and try to understand their logic.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

5
3 4 2 1 5
5
2 3 2 3 1
0

Output:

1 2 3 4 5
1 2 2 3 3

Counting Sort Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Counting Sort
 */

#include<stdio.h>
#include<string.h>

static unsigned A[128];

int main(){
    register unsigned n, i, c;
    unsigned num;
    while(scanf("%u", &n) && n){             /* Test cases */
        memset(A, 0, sizeof A);              /* Clear memory for each test case */
        for(i = n; i; --i){                  /* Exits Loop when i is 0 */
            scanf("%u", &num);
            ++A[num];                        /* Since input is never greater than 100, we can use that as index and count occurrence of that index */
        }
        c = i = 1;                           /* i starts from 1 since i is never 0  */
        for(; i<100; ++i){
            while(A[i]--){                   /* Decrease number count at that index */
                if(c == n) printf("%u", i);  /* For the last item in sorted output there is no space */
                else{
                    printf("%u ", i);        /* Just print the index since that was our original input */
                    ++c;                     /* Counter to check if the last element is reached */
                }
            }
        }
        printf("\n");                        /* Print a new line for each test case */
    }
    return 0;
}

 Counting Sort Code ( Usage of stringstream, *slower ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Description: stringstream demo
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>

using namespace std;

static unsigned A[128];

int main(){
    register unsigned n, c, i;
    unsigned num;
    string B;
    while(1){
        scanf("%u", &n); getchar();
        if(!n) return 0;

        memset(A, 0, sizeof A);
        getline(cin, B);

        stringstream ss;
        ss << B;
        while(ss >> num)
            ++A[num];


        c = i = 1;
        for(; i < 100; ++i){
            while(A[i]--){
                if(c == n) printf("%u", i);
                else{
                    printf("%u ", i);
                    ++c;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

 Binary Merge Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Binary Merge Sort ( 2 Partition )
 */

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid, register unsigned rear){
    register unsigned n1 = mid-front+1;         /* Calculate size of left half of the array */
    register unsigned n2 = rear - mid;          /* Calculate size of right half of the array */

    unsigned *L = new unsigned[n1 + 1];     /* Dynamically create and allocate calculated amount of memory */
    unsigned *R = new unsigned[n2 + 1];     /* plus 1 to hold Infinity or A Very large value for which any input can't be larger than */

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front+i];                          /* Copy elements from given original array to left sub array */

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];                          /* Copy elements from given original array to right sub array */


    L[n1] = INT_MAX;                                /* In the last position of sub array set a very large value */
    R[n2] = INT_MAX;
    i = j = 0;

    register unsigned k = front;                /* Instead of wasting space creating a new array, we can use the original large array since we have already copied all items to sub arrays */
    for(; k <= rear; ++k){
        if(L[i] <= R[j])
            A[k] = L[i++];             /* Compare and copy smaller elements of sub arrays onto original array */
        else
            A[k] = R[j++];
    }
}

void Mergesort(register unsigned front, register unsigned rear){
    if(front < rear){
       register unsigned mid = (rear+front) >> 1;  /* Find the mid point of the array */
                                                    /* Shift bits to right once, equivalent of divided by TWO */

       Mergesort(front, mid);                       /* Recursively divide array in left portion */
       Mergesort(mid+1, rear);                      /* Recursively divide array in right portion */

       Merge(front, mid, rear);                     /* Merge the divided array back again in sorted order */
    }
}

int main(){
    register unsigned n, i;
    while(scanf("%u", &n) && n){
        for(i=0; i<n; ++i)
            scanf("%u", &A[i]);

        Mergesort(0, n-1);                          /* Call merge sort function for each test case */

        for(i = 0; i<n; ++i){
            printf("%u", A[i]);
            if(i != n - 1)
                printf(" ");                 /* Do not print a space after last sorted item */
        }
        printf("\n");
    }
    return 0;
}

 Ternary Merge Sort Code ( 3 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Ternary Merge Sort ( 3 Partition )
 */

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid1, register unsigned mid2, register unsigned rear){
    /*
     * Calculate size for creating sub array
     * In this case calculate size for three sub arrays
     */
    unsigned n1 = mid1 - front + 1;
    unsigned n2 = mid2 - mid1;
    unsigned n3 = rear - mid2;

    /*
     * Dynamically allocate memory for three sub arrays
     * Here Plus One because we will set a very large value for last position of the array
     */
    unsigned *L = new unsigned[n1 + 1];
    unsigned *R = new unsigned[n2 + 1];
    unsigned *X = new unsigned[n3 + 1];

    /*
     * Copy 1/3 of original array to sub arrays
     * First 1/3 to L array, next 1/3 to R array, last 1/3 to X array
     */
    register  int i = 0;
    for(; i<n1; ++i)
        L[i] = A[front + i];

    for(i=0; i<n2; ++i)
        R[i] = A[mid1 + 1 + i];

    for(i = 0; i < n3; ++i)
        X[i] = A[mid2 + 1 + i];

    /*
     * INT_MAX is found in <limits.h>
     * Instead of traversing the whole array increasing runtime
     * We can compare every element again a very large value which will always be grater than or equal to any input
     */
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    X[n3] = INT_MAX;

    /*
     * Reset index counter for sorting
     */
    i = 0;
    register unsigned p = 0, j = 0, k = front;

    /*
     * Sort:
     * Compare items of each array against each other
     * Copy back the smaller item from the comparison to original array
     */
    for(; k <= rear; ++k){
        if(L[i] <= R[j] && L[i] <= X[p]){
            A[k] = L[i];
            ++i;
        }else if(R[j] <= X[p]){
            A[k] = R[j];
            ++j;
        }else{
            A[k] = X[p];
            ++p;
        }
    }
}

void Mergesort(register int front, register int rear){
    /*
     * Check if there is only One element in array
     */
    if(front < rear){
        /*
         * calculate the size of 1/3 of array
         * Now calculate two mid points since it is 3 way partition
         */
        register int dist = (rear - front + 1) / 3;
        int mid1 = front + dist;
        int mid2 = mid1 + dist;

        /*
         * Recursively call this array cutting down original array by 1/3 ( One Third )
         */
        Mergesort(front, mid1);
        Mergesort(mid1 + 1, mid2);
        Mergesort(mid2 + 1, rear);

        /*
         * Merge divided elements back into original array
         */
        Merge(front, mid1, mid2, rear);
    }
}

int main(){
    register int n, i;
    while(scanf("%u", &n) && n){
        for(i = 0; i < n; ++i)
            scanf("%u", &A[i]);

        /*
         * Merge sort from index 0 to index n-1
         */
        Mergesort(0, n - 1);

        for(i = 0; i < n; ++i){
            printf("%u", A[i]);
            /*
             * For the last sorted element do not print a space
             */
            if(i != n-1)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

 Quick Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Quick Sort ( 2 Partition )
 */
#include<cstdio>
#include<iostream>

#define SIZE 2000002

static int A[SIZE];

void quicksort (int *a, register int n) {
    register int i, j, mid;
    if (n < 2) return;

    mid = a[n >> 1];

    for (i = 0, j = n - 1; ; i++, j--) {
        while (a[i] < mid)
            i++;
        while (mid < a[j])
            j--;

        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    quicksort(a, i);
    quicksort(a + i, n - i);
}

int main () {
    register unsigned n, i;
    while(scanf("%u", &n) && n){
        for(i = 0; i < n; ++i)
            scanf("%d", &A[i]);

        quicksort(A, n);

        for (i = 0; i < n; i++)
            printf("%d%s", A[i], i == n - 1 ? "\n" : " ");

    }
    return 0;
}

 Quick Sort Code ( 3 Partition ):

/* To Do */