Menu
The following algorithm can sort three variables x, y and z of type K which are comparable using operator<:
void sort2(K& x, K& y) { if(y < x) swap(x, y); } void sort3(K& x, K& y, K& z) { sort2(x, y); sort2(y, z); sort2(x, y); } This needs three swaps in the "worst case". However basic mathematics tells us, that the ordering of three values can be done using only two swaps.
Example: The values (c,b,a) will be sorted using three swaps: (c,b,a) -> (b,c,a) -> (b,a,c) -> (a,b,c). However one swap would have been enough: (c,b,a) -> (a,b,c).
What would be the simplest algorithms which sorts three variables with at most two swaps in all cases?
240
Insertion sort – Worst Case input for maximum number of swaps will be already sorted array in ascending order. When a new element is inserted into an already sorted array of k size, it can lead to k swaps (in case it is the smallest of all) in worst case.
To swap three numbers, first, we initialize three variables i.e. first_number, second_number, and third_number. With these three numbers, a temporary variable named temp is also initialized to store a number temporarily. Then scan allows the user to assigned numbers according to their wish.
Insertion Sort is suitable for arrays of small size. It also achieves best-case complexity of O(n) if the arrays are already sorted.
Method 1 (Using Arithmetic Operators) The idea is to get sum in one of the two given numbers. The numbers can then be swapped using the sum and subtraction from sum.
Find the smallest, this takes 2 comparisons, and swap it into the first position. Then compare the remaining 2 and swap if necessary.
if (x < y) { if (z < x) swap(x,z); } else { if (y < z) swap(x,y); else swap(x,z); } if(z<y) swap(y,z); This takes 3 comparisons, but only two swaps.
68
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
