UVA – 10327 – Flip Sort

you can use merge sort to solve it in O(nlogn), if you are confused about the absence of the flip operation, read the problem statment carefully.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		while (in.hasNext()) {
			int n = in.nextInt();
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = in.nextInt();
			}

			int count = flipSort(a);
			System.out.printf("Minimum exchange operations : %d\n", count);
		}
	}

	private static int flipSort(int[] a) {

		int flips = 0, n = a.length;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) { 				if (a[i] > a[j]) {
					flips++;
				}
			}
		}
		return flips;
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: