Modified bucket sort

Question

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;
   }

JS1 · Accepted Answer · 2017-04-21 10:51:11Z

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.

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

Stack Exchange Network

Modified bucket sort

1 Answer 1

Pointless loops

Way too complicated

You must log in to answer this question.

Hot Network Questions

Modified bucket sort

1 Answer 1

Pointless loops

Way too complicated

You must log in to answer this question.

Related

Hot Network Questions