# Modified bucket sort

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


### 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 Apr 21 '17 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 Apr 21 '17 at 14:19