4
\$\begingroup\$

The code runs fine and the algorithm is much faster than insertion sort. I built a modified bucket sort around the parameters given in the HW to sort a vector of ints with 50 iterations and 40000 items.

Being new and not familiar with bucket sorts I haven't found any code examples quite like this one. So my question is about my style and possible room for optimization. How can I streamline this algorithm?

void intVectSort2(vector<int> &V, int M)
   {
     // declare size for U and V
     int uSize = ((M * 2) + 1);
     int vectSize = V.size();

     // allocate memory for U array and initialize to zeros
     int *U = new int[uSize];
     for (int i = 0; i < uSize; i++)
       U[i] = 0;

     // step through M values and increment U when V is equal to M
     for (int j = 0; j < vectSize; j++)
       {
         int val = 0;
         int count = 0;
         int element = 0;
         int iterator = M;
         val = V[j];
         while (val != iterator)
           iterator--;
         element = iterator + M;
         count = U[element];
         count++;
         U[element] = count;
       }

     //load confirmed values in order back into V
     int index = 0;
     int currentSize = 0;
     for (int k = 0; k < uSize; k++)
       {
         int value = 0;
         int counter = 0;
         value = U[k];
         if (value != 0)
           {
             while (counter < value)
             counter++;
             currentSize += counter;
             for (index; index < currentSize; index++)
               V[index] = k - M;
           }
       }

     // free dynamic memory
     delete [] U;
   }
\$\endgroup\$
2
\$\begingroup\$

Pointless loops

You have a couple of loops that do nothing but waste time:

     while (val != iterator)
       iterator--;

That loop does the same thing as:

    iterator = val;

Similarly, this loop:

         while (counter < value)
         counter++;

is the same as:

         counter = value;

Way too complicated

Your code that fills the buckets is confused and complicated:

 for (int j = 0; j < vectSize; j++)
   {
     int val = 0;
     int count = 0;
     int element = 0;
     int iterator = M;
     val = V[j];
     while (val != iterator)
       iterator--;
     element = iterator + M;
     count = U[element];
     count++;
     U[element] = count;
   }

It should really be a one line loop:

for (int j = 0; j < vectSize; j++) {
    U[V[j]]++
}

Note that this uses buckets in the range 0..M, whereas yours uses buckets in the range M..2M for no good reason.

Similarly, your bucket unpacking loop could be simplified to:

int index = 0;
for (int i = 0; i <= M; i++) {
    for (int j = 0; j < U[i]; j++) {
        V[index++] = i;
    }
}

This assumes that you allocated U to hold M+1 elements, to allow for values in the range 0..M.

\$\endgroup\$
  • \$\begingroup\$ Thank you @JS1, this is exactly the kind of feedback I need right now. I appreciate your time :) https://www.linkedin.com/in/victorchimenti/ \$\endgroup\$ – Vic Apr 21 '17 at 14:15
  • 1
    \$\begingroup\$ @Vic, if you want people to have access to you linkedin profile, you can put the link into your profile here. \$\endgroup\$ – Stephen Rauch Apr 21 '17 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.