package day2x.day20.sorting;

import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Created by jsong on 20/03/2017.
 * <p>
 * hackerrank	: https://www.hackerrank.com/jsong00505
 * github		: https://github.com/jsong00505
 * linkedin		: https://www.linkedin.com/in/junesongskorea/
 * email		: jsong00505@gmail.com
 * <p>
 * challenge	: Day 20: Sorting
 */
public class Solution {
	public static void main(String[] args) {
		try(
			Scanner in = new Scanner(System.in);
			PrintWriter out = new PrintWriter(System.out);
		) {
			// get number of elements
			int n = in.nextInt();
			// init array size as the number
			int a[] = new int[n];

			// get element from user
			for(int i = 0; i < n; i++){
				a[i] = in.nextInt();
			}

			// count how many time swap the elements
			int count = 0;
			// bubble sorting
			for(int i = 0; i < n; i++) {
				// Track if a swap was made
				boolean swapped = false;

				for(int j = 0; j < n-1; j++) {
					// check if it needs swap
					if(a[j] > a[j+1]) {
						int temp = a[j];
						a[j] = a[j+1];
						a[j+1] = temp;

						swapped = true;
						// increase the count
						count++;
					}
				}

				// Terminate loop as soon as array is sorted
				if(!swapped) {
					break;
				}
			}

			// print
			out.printf("Array is sorted in %d swaps.\n", count);
			out.printf("First Element: %d\n", a[0]);
			out.printf("First Element: %d\n", a[a.length-1]);
		}catch(Exception e) {
			e.printStackTrace();
		}
	}
}

@@ -578,16 +578,67 @@
 tInt();%0A
+%0A%09%09%09// constraints%0A%09%09%09assert(n %3E= 2 && n %3C= 600);%0A%0A
 %09%09%09// in
@@ -675,12 +675,12 @@
 %09int
- a
 %5B%5D
+ a
  = n
@@ -774,16 +774,92 @@
 xtInt();
+%0A%0A%09%09%09%09// constraints%0A%09%09%09%09assert(a%5Bi%5D %3E= 1 && a%5Bi%5D %3C= (2 * Math.pow(10, 6)));
 %0A%09%09%09%7D%0A%0A%09
@@ -919,16 +919,58 @@
 nt = 0;%0A
+%09%09%09// optimize one%0A%09%09%09int endOffset = 0;%0A%0A
 %09%09%09// bu
@@ -1096,18 +1096,28 @@
 j = 
-0
+1
 ; j %3C n
--1
+ - endOffset
 ; j+
@@ -1167,17 +1167,19 @@
 (a%5Bj
+ - 1
 %5D %3E a%5Bj
-+1
 %5D) %7B
@@ -1199,16 +1199,20 @@
 mp = a%5Bj
+ - 1
 %5D;%0A%09%09%09%09%09
@@ -1219,17 +1219,19 @@
 %09a%5Bj
+ - 1
 %5D = a%5Bj
-+1
 %5D;%0A%09
@@ -1242,10 +1242,8 @@
 %09a%5Bj
-+1
 %5D = 
@@ -1409,24 +1409,42 @@
 break;%0A%09%09%09%09%7D
+%0A%0A%09%09%09%09endOffset++;
 %0A%09%09%09%7D%0A%0A%09%09%09//
@@ -1557,35 +1557,34 @@
 %0A%09%09%09out.printf(%22
-Fir
+La
 st Element: %25d%5Cn

add constraints and optimize the sorting