Menu
I am stuck with a problem and I need some help from bright minds of SO. I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped with each other. Sometimes there is no solution, so I need to throw an exception then.
Example:
in pairs: 1 5 7 1 3 8 5 6 out pairs: 1 7 <-- swapped 1 5 6 5 <-- swapped 8 3 <-- swapped ^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result. or
in pairs: 1 5 6 9 out: not possible One more example that shows how 'sorting pairs' first isn't the solution.
in pairs: 1 4 2 5 out pairs: 1 4 5 2 Thanks
706
Since all sorting algorithms are bound below by Ω(n), I would argue that both radix sort and bucket sort are the fastest algorithms for sorting an array of integers.
But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
O( n log n ) solution
166
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
