Writing two versions of a function, one for "clarity" and one for "speed"

Question

My professor assigned homework to write a function that takes in an array of integers and sorts all zeros to the end of the array while maintaining the current order of non-zero ints. The constraints are:

Cannot use the STL or other templated containers. Must have two solutions: one that emphasizes speed and another that emphasizes clarity.

I wrote up this function attempting for speed:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

void sortArray(int array[], int size)
{
    int i = 0;
    int j = 1;
    int n = 0;
    for (i = j; i < size;)
    {
        if (array[i] == 0)
        {
            n++;
            i++;
        }
        else if (array[i] != 0 && j != i)
        {
            array[j++] = array[i++];
        }
        else
        {
            i++;
            n++;
        }
    }
    while (j < size)
    {
        array[j++] = 0;
    }
}

int main()
{
    //Example 1
    int array[]{20, 0, 0, 3, 14, 0, 5, 11, 0, 0};
    int size = sizeof(array) / sizeof(array[0]);
    sortArray(array, size);
    cout << "Result :\n";
    for (int i = 0; i < size; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl << "Press any key to exit...";
    cin.get();
    return 0;
}

It outputs correctly, but;

• I don't know what the speed of it actually is, can anyone help me figure out how to calculate that?
• I have no idea how to go about writing a function for "clarity"; any ideas?

Answer 1

I my experience, unless you have very complicated algorithm, speed and clarity come together:

void sortArray(int array[], int size)
{
  int item;
  int dst = 0;
  int src = 0;

  // collect all non-zero elements
  while (src < size) {
    if (item = array[src++]) {
      array[dst++] = item;
    }
  }

  // fill the rest with zeroes
  while (dst < size) { 
    array[dst++] = 0;
  }
}

Speed comes from a good algorithm. Clarity comes from formatting, naming variables and commenting.

Answer 2

Speed as in complexity?

Since you are, and need, to look at all the elements in the array — and as such have a single loop going through the indexes in the range [0, N)—where N denotes the size of the input—your solution is O(N).

Further reading:

• Plain English explanation of big O
• Determining big O Notation

---

Regarding clearity

In my honest opinion there shouldn't need to be two alternatives when implementing such functionality as you are presenting. If you rename your variables to more suitable (descriptive) names your current solution should be clear enough to count as both performant and clear.

Your current approach can be written in plain english in a very clear fashion:

pseudo-explanation

• set write_index to 0
• set number_of_zeroes to 0
• For each element in array
  • If element is 0
  • increase number_of_zeros by one
  • otherwise
  • write element value to position denoted by write_index
  • increase write_index by one
• write number_of_zeroes 0s at the end of array

Having stated the explanation above we can quickly see that sortArray is not a descriptive name for your function, a more suitable name would probably be partition_zeroes or similar.

Adding comments could improve readability, but you current focus should lie in renaming your variables to better express the intent of the code.

Answer 3

^{(I feel your question is almost off-topic; I am answering it from a Linux perspective; I recommend using Linux to learn C++ programming; you'll adapt my advices to your operating system if you are using something else....)}

speed

Regarding speed, you should have two complementary approaches.

The first (somehow "theoretical") is to analyze (i.e. think on) your algorithm and give (with some proof) its asymptotic time complexity.

The second approach (only "practical", and often pragmatical) is to benchmark and profile your program. Don't forget to compile with optimizations enabled (e.g. using g++ -Wall -O2 with GCC). Have a benchmark which runs for more than half of a second (so processes a large amount of data, e.g. several million numbers) and repeat it several times (e.g. using time(1) command on Linux). You could also measure some time inside your program using e.g. <chrono> in C++11, or just clock(3) (if you read a large array from some file, or build a large array of pseudo-random numbers with <random> or with random(3) you certainly want to measure separately the time to read or fill the array with the time to move zeros out of it). See also time(7).

^{(You need to process a large amount of data - more than a million items, perhaps many millions of them - because computer are very fast; a typical "elementary" operation -a machine instruction- takes less than a nanosecond, and you have lot of uncertainty on a single run, see this)}

clarity

Regarding clarity, it is a bit subjective, but you might try to make your code readable and concise. Adding a few good comments could also help. Be careful about naming: sorting is not exactly what your program is doing (it is more moving zeros than sorting the array)...

Answer 4

I think this is the best - Of course you may wish to use doxygen or some other

// Shift the non-zeros to the front and put zero in the rest of the array
void moveNonZerosTofront(int *list, unsigned int length)
{
   unsigned int from = 0, to = 0;

   // This will move the non-zeros
   for (; from < length; ++from) {
      if (list[from] != 0) {
          list[to] = list[from];
          to++;
      }
   }

   // So the rest of the array needs to be assigned zero (as we found those on the way)
   for (; to < length; +=to) {
     list[to] = 0;
   }
}