702996. Sort in specific order
Easy
Here is the Markdown blog post for the problem "Sort in specific order":
# Sort in specific order
## Slug: sort-in-specific-order2422
## Difficulty: Easy
## Id: 702996
## Topic Tags: Arrays, Sorting, Data Structures, Algorithms, Numbers
## Company Tags: Zoho, Microsoft
### Summary
Given an array of integers, sort the elements in a specific order based on their values. The sorting should be done as follows:
- All even numbers should come first.
- Then, all odd numbers should come next.
- Within each group (even or odd), the numbers should be sorted in ascending order.
### Detailed Explanation
To solve this problem, we can use a simple algorithm that involves iterating over the array and placing elements into two separate arrays: one for even numbers and another for odd numbers. Once we have these two arrays, we sort them individually using the built-in sorting function of our programming language (e.g., `Arrays.sort()` in Java). Finally, we concatenate the sorted even and odd arrays to get the final result.
Here is a step-by-step breakdown of the solution:
1. Initialize two empty arrays: `evenNumbers` and `oddNumbers`.
2. Iterate over the input array. For each element:
- If the element is even, add it to the `evenNumbers` array.
- If the element is odd, add it to the `oddNumbers` array.
3. Sort the `evenNumbers` array in ascending order using the built-in sorting function.
4. Sort the `oddNumbers` array in ascending order using the built-in sorting function.
5. Concatenate the sorted `evenNumbers` and `oddNumbers` arrays to get the final result.
Time complexity: O(n log n) due to the sorting of the even and odd arrays (where n is the length of the input array).
Space complexity: O(n) for storing the even and odd arrays.
### Optimized Solutions
#### Java
public class SortInSpecificOrder {
public static int[] sort(int[] arr) {
int[] evenNumbers = new int[0];
int[] oddNumbers = new int[0];
for (int num : arr) {
if (num % 2 == 0) {
evenNumbers = Arrays.copyOf(evenNumbers, evenNumbers.length + 1);
evenNumbers[evenNumbers.length - 1] = num;
} else {
oddNumbers = Arrays.copyOf(oddNumbers, oddNumbers.length + 1);
oddNumbers[oddNumbers.length - 1] = num;
}
}
int[] result = new int[evenNumbers.length + oddNumbers.length];
System.arraycopy(evenNumbers, 0, result, 0, evenNumbers.length);
System.arraycopy(oddNumbers, 0, result, evenNumbers.length, oddNumbers.length);
Arrays.sort(result);
return result;
}
}