CODEWITHSUNDEEP
cswitch-statementperformance
user1999073
user1999073

Reputation: 106

Efficiency of the switch statement

I'm currently writing an implementation of the quicksort algorithm, and I have a question of efficiency, specifically about partitioning the array. The way I'm partitioning the array before sorting involves choosing the pivot, or partitioning element, to be the first element in the array (I know. not the most efficient way of doing it) and then setting up two variables- "high" and "low"- to be the last index and the first index of the array respectively. I have a while loop setup that partitions the array by switching certain elements around and incrementing and decrementing low and high until they are equal.

My question is that I'm using a switch statement to control which index to move instead of setting up two separate while loops to do that. Is using a switch statement more efficient in this case?

Here is the relevant code:

    //used to determine which side of the array to move the element to
    #define RIGHT 1
    #define LEFT 0

    void partition( int nums[], int size )
    {
         int pivot = nums[0], low = 0, high = size - 1, turn = LEFT;

         while ( low != high )
         {

             switch (turn)
             {
                case RIGHT:
                     if ( nums[low] >= pivot )
                     {
                         nums[high] = nums[low];
                         high--;
                         turn = LEFT;
                     }
                     else
                         low++;
                     break;

                case LEFT:
                     if ( nums[high] <= pivot )
                     {
                         nums[low] = nums[high];
                         low++;
                         turn = RIGHT;
                     }
                     else
                         high--;
                     break;
            }
        }

        nums[low] = pivot;
     }

Upvotes: 0

Views: 251

Answers (2)

DigitalRoss
DigitalRoss

Reputation: 146063

My guess is two loops, but measure

It's generally better to move invariant expressions outwards from loops. This optimization is called code hoisting. or loop-invariant code motion. It wins for the obvious reason. Now, in your case, it's not obvious to the compiler what is invariant but you know that the turn variable is less variant than low and high.

So, my guess is that two loops is better, but the only way to know for sure is to measure it.

Upvotes: 1

DrC
DrC

Reputation: 7698

You cannot know without actually testing. Compilers can do amazing things some times (both amazingly good and bad). In general, I would expect it to be faster moving to two loops because the state is held in the program counter but the compiler may do that or better. It will also vary with the optimization settings on the compile.

Upvotes: 1

Related Questions