question
You are given an array containing odd and even numbers. Sort the array so that all
the odd numbers are before the even numbers. Also, the odd half of the array should
be sorted in descending order while the even half should be sorted in ascending order.
You cannot use an additional array and the sorts must be done in-place. Additionally,
you cannot do any pre/post processing.
ex. An input array: [14, 12, 3, 10, 11, 1, 7, 26, 8]
returns: [11, 7, 3, 1, 8, 10, 12, 14, 26]
ex. An input array: [14, 12, 3, 10, 11, 1, 7, 26, 8]
returns: [11, 7, 3, 1, 8, 10, 12, 14, 26]
Think of all the in-place sorting algorithms you know. Use similar principals to separate even and odd elements.
Input: [14, 12, 3, 10, 11, 1, 7, 26, 8]
We'll first keep two values, 'start' and 'end', that will initially hold the position of the beginning and end of the array.
Increment the 'start' value until an even element is found (value % 2 == 0)
Decrement the 'end' value until an odd element is found (value % 2 != 0)
Swap the elements at 'start' and 'end'.
Repeat the above three steps while start < end.
[7, 1, 3, 11, 10, 12, 14, 26, 8]
When start = end we will have the position of an element on the dividing line between even and odd. To finish the task, use any standard in-place sorting algorithm such as insertion sort to appropriately sort odd elements in descending order and even elements in ascending order.
Have a better solution? Let us know in the comments below!
We'll first keep two values, 'start' and 'end', that will initially hold the position of the beginning and end of the array.
Increment the 'start' value until an even element is found (value % 2 == 0)
Decrement the 'end' value until an odd element is found (value % 2 != 0)
Swap the elements at 'start' and 'end'.
Repeat the above three steps while start < end.
[7, 1, 3, 11, 10, 12, 14, 26, 8]
When start = end we will have the position of an element on the dividing line between even and odd. To finish the task, use any standard in-place sorting algorithm such as insertion sort to appropriately sort odd elements in descending order and even elements in ascending order.
Have a better solution? Let us know in the comments below!