bucket sort algorithm. any optimization tips?

[E3h7X9L8]

  #include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <limits>
using std::numeric_limits;
using std::streamsize;

#include <iomanip>
using std::setw;

#include <vector>
using std::vector;

#include <cmath>
using std::pow;

#include <cstdlib>
using std::rand;

#include <ctime>
using std::srand;

const int GLOBAL_SIZE = 10000;

void bucketSort(int [], int);
void printArray(int [], int);

int main()
{
	srand(time(0));

	int data[::GLOBAL_SIZE];

	int size,answer;

	cout << "Enter array size(max 10000): ";
	cin >> size;

	cout << "\nDo you want to fill the array with random elements between 1-size?\n\n"
		<< "If yes, enter 1\n"
		<< "If no enter any number\n\n"
		<< "Answer: ";
	cin >> answer;
	
	switch (answer)
	{
	case 1:
		for (int i = 0; i < size; i++)
		{
			data[i] = 1 + rand() % size;
		}
		break;
	default:
		cout << endl;
		for (int i = 0; i < size; i++)
		{
			cout << "Element " << i + 1 << " is: ";
			cin >> data[i];
		}
		break;
	}

    bucketSort(data, size);
	printArray(data, size);
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();

	return 0;
}

void bucketSort(int data[], int size)
{
	int bucket[10][::GLOBAL_SIZE];
	
	for (int q = 0; q < 10; q++)
	{
		for (int w = 0; w < size ; w++)
			bucket[q][w] = 0;
	}

	int digit;
	bool sorted = false;
	int powCounter = 0;

	while (sorted == false)
	{
		int counters[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
		sorted = true;

		for (int i = 0; i < size; i++)
		{
			digit = ( data[i] / static_cast<int>(pow(10, powCounter)) ) % 10;
			bucket[digit][counters[digit]] = data[i];
			counters[digit]++;
		}

		//In case you want to see the algorithm in action remove /* */
		/*for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < size; j++)
				cout << setw(3) << bucket[i][j];
			cout << endl;
		}
		system("pause");*/ 

		if (bucket[0][size - 1] == 0)
			sorted = false;
		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < size; j++)
			{
				if (bucket[i][j] != 0)
				{
					data[counters[10]] = bucket[i][j];
					bucket[i][j] = 0;
					counters[10]++;
				}
			}
		}
		powCounter++;
	}

}

void printArray(int data[], int size)
{
	for (int i = 0; i < size; i++)
	{
		if (i % 10 == 0)
			cout << endl;
		cout << setw(7) << data[i];
	}
}

[MokkaTech]

Hey there,

IMHO you should leave out the "using" declarations, as they are bad form.
And it is always better to know for debugging, out of which namespace (or class) the functions are.

Secondly, while you are declaring the functions in lines 27f, you should also declare the variables, i.e. not just (int [], int), but (int data[], int size). This also just pro forma...

Additionally you should declare and initialise the boolean in line 84 at the beginning of the programm, --> globally, and THEN set the value to FALSE in the function.

In the while loop, in line 90, you are setting the bool sorted to TRUE

Pro forma I would also do that at the very end of the loop, just an aesthetic aspect.

For the for-loop in line 110, you should use another variable as the counter, too. Again, a thing that is just very optional, but helps to structure down your code.

This is no criticism at all, btw. The code itseld looks nice and dandy. Maybe you could have put the two function (printArray and bucketSort) in an additional header file, maybe even a class. But this, once again, are just proposals to make your code look a lot nicer ;)

Cheers

Mokka



P.S.: Use indents: Not just to strip down the code a bit, but also to structure variables etc.

From here on there will the small adjustments I did on your program The indents are not printing correctly :/ Sorry

[MiiNiPaa]

In the while loop, in line 90, you are setting the bool sorted to TRUE

Pro forma I would also do that at the very end of the loop, just an aesthetic aspect.

...That would break algorithm. It is a common pattern, btw.

For the for-loop in line 110, you should use another variable as the counter, too

I do not see any problems with variables (aside that they could be named better)


I would suggest to roll out your own integer pewer function: it would work better and faster than cmath one. Or even better, initialize powCounter to 1 and instead of incrementing it at the end, multiply it by 10. Ther replace whole static_cast<int>(pow(10, powCounter)) with just powCounter .

int bucket[10][::GLOBAL_SIZE]; arrays that large should not go on stack. You have just exhausted 40% of total stack size on my compiler settings.

[E3h7X9L8]

thanks for replying guys, i took your advices and improved my code.