The best method of sorting 3 values using if-statement

  c++, if-statement, sorting

I’ve found an exercise in "Programming principles and practice by B. Stroustrup’s" that asks to write a program to sort 3 integer values using if-else statement.

  • I’ve tried a lot and found myself the swapping method although later on I’ve found it already done on the internet:

    int x = 3, y = 5, z = 1;
    if(y < x)
       swap(x, y);
    if(y < z)
       swap(y, z);
    if(y < x)
        swap(x, y);
    
  • Although it works just fine but that simple line function-call (swap(A, B)) has a significant cost behind the curtain: A temporary and Copy:

     if(y < x){
        auto tmp = x;
        x = y;
        y = tmp;
     }
    

As you can see it is called at least 2 times in the worst cases like 5 2 7.

  • I’ve tried a lot and written down all possible permutations until I’ve discovered this solution:

1- Declare three integer values, let’s say min, mid, max.

2- Set min to value of x, max to y‘s and mid to z.

3- mid (z) initial value has 6 possibilities: 2 correct and 4 wrong:

2 7 5 -> mid = 5 correct
7 2 5 -> mid = 5 correct
2 5 7 -> mid = 7 incorrect -> mid has max value
5 2 7 -> mid = 7 incorrect -> mid has max value
5 7 2 -> mid = 2 incorrect -> mid has min value
7 5 2 -> mid = 2 incorrect -> mid has min value
  • So The first thing we do is to check whether min and max of x and y are correct otherwise swap min and max:

    if(y < x){
        min = y;
        max = x;
    }
    
  • Now we have correct min and max.

  • Check whether z is (previous value of mid) greater than max and if so we swap max and mid (z):

     if(max < z){
         mid = max; // update mid to the previous value of max
         max = z; // update max to the previous value of mid (z)
     }
    
  • Check whether z (previous value of mid) is less than min and if so we swap min and mid (z):

    if(z < min){
        mid = min;
        min = z;
    }
    
  • Now everything works fine. Here is the full example:

      int main(){
    
          int x = 2, y = 5, z = 7;
          int min = x, max = y, mid = z; 
    
          if(y < x){
              min = y;
              max = x;
          }
          if(max < z){ 
              mid = max;
              max = z;
          }
          if(z < min){
              mid = min;
              min = z;
          }
    
          std::cout << min << ", " << mid << ", " << max << 'n';
    
      }
    
  • Is my analysis rational? Is my program efficient? Can we depend on it as the best implementation of sorting three values? Any Tip, comment is highly appreciated.

  • Input:

    2 5 7
    2 7 5
    5 2 7
    5 7 2
    7 2 5
    7 5 2
    
  • Output:

    2, 5, 7
    2, 5, 7
    2, 5, 7
    2, 5, 7   
    2, 5, 7
    

Source: Windows Questions C++

LEAVE A COMMENT