Problem Statement

You are given a int[] data, and you must order the elements of data such that no two consecutive elements have consecutive values. In other words, result[i] + 1 != result[i + 1] for all i, where 0 <= i < n-1, and n is the number of elements in data. If more than one ordering exists, return the one that comes first lexicographically.

Definition

 Class: WeirdSort Method: sortArray Parameters: int[] Returns: int[] Method signature: int[] sortArray(int[] data) (be sure your method is public)

Constraints

-data will contain between 1 and 50 elements, inclusive.
-Each element of data will be between 0 and 1000, inclusive.

Examples

0)

 `{1, 2}`
`Returns: {2, 1 }`
 Only one possible ordering exists.
1)

 `{1, 2, 3}`
`Returns: {1, 3, 2 }`
 There are only three possible orderings: {1, 3, 2}, {2, 1, 3} and {3, 2, 1}. The first one is lexicographically smallest.
2)

 `{1, 1, 1, 1, 2, 2, 2, 2, 2}`
`Returns: {2, 2, 2, 2, 2, 1, 1, 1, 1 }`
 All 2's should be before 1's.
3)

 `{1, 2, 3, 4, 5, 6}`
`Returns: {1, 3, 2, 4, 6, 5 }`
4)

 `{1, 1, 2, 2, 3, 3}`
`Returns: {1, 1, 3, 3, 2, 2 }`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6755

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10001&pm=6755

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Sorting