even odd numbers sort | Algorithms, Data Structures, and Programming
Given n random numbers. Move all even numbers on left hand side and odd numbers on right hand side and then sort the even numbers in increasing order and odd numbers in decreasing order
For example, i/p : 3 6 9 2 4 10 34 21 5
o/p: 2 4 6 10 34 3 5 9 21
Sort all even numbers in ascending order and then sort all odd numbers in descending order
Method 1 (Using Partition)
Method 2 (Using negative multiplication) :
Read full article from even odd numbers sort | Algorithms, Data Structures, and Programming
Given n random numbers. Move all even numbers on left hand side and odd numbers on right hand side and then sort the even numbers in increasing order and odd numbers in decreasing order
For example, i/p : 3 6 9 2 4 10 34 21 5
o/p: 2 4 6 10 34 3 5 9 21
public Integer[] evenOddSort(Integer[] a){ int i, j; i=0; j = a.length-1; // move even numbers in first half and odd numbers in secound half while(i < j ){ // even number then go further if(a[i]%2 == 0){ i++; } // odd number then go further else if(a[j]%2 == 1) { j--; } else if(a[i]%2 == 1 && a[j]%2 == 0){ swap(a, i, j); i++; j--; } } // keep the boundary of even and odd indexes correctly if(a[i]%2 == 0) { i++; } // sort even numbers in ascending order Arrays.sort(a, 0, i); // sort odd numbers in descending order Arrays.sort(a, i, a.length, Collections.reverseOrder()); return a; } private void swap(Integer[] a, int i, int j){ int temp = a[i]; a[i]=a[j]; a[j]=temp; }Sort all even numbers in ascending order and then sort all odd numbers in descending order
- Partition the input array such that all odd elements are moved to left and all even elements on right. This step takes O(n).
- Once the array is partitioned, sort left and right parts individually. This step takes O(n Log n).
void twoWaySort(int arr[], int n){ // Current indexes from left and right int l = 0, r = n-1; // Count of odd numbers int k = 0; while (l < r) { // Find first odd number from left side. while (arr[l]%2 != 0) { l++; k++; } // Find first even number from right side. while (arr[r]%2 == 0 && l<r) r--; // Swap odd number present on left and even // number right. if (l < r) swap(arr[l], arr[r]); } // Sort odd number in descending order sort(arr, arr+k, greater<int>()); // Sort even number in ascending order sort(arr+k, arr+n);}- Make all odd numbers negative.
- Sort all numbers.
- Revert the changes made in step 1 to get original elements back.
void twoWaySort(int arr[], int n){ // Make all odd numbers negative for (int i=0 ; i<n ; i++) if (arr[i] & 1) // Check for odd arr[i] *= -1; // Sort all numbers sort(arr, arr+n); // Retaining original array for (int i=0 ; i<n ; i++) if (arr[i] & 1) arr[i] *= -1;}