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;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s