Binsort implementation 桶排序实现

Binsort is a classical implementation of the idea that sacrificing space to improve efficiency. 

本例实现桶排序，这是算法分析中一个经典的以空间换时间的案例。桶排序以被排序数组的数据作为新数组的下标，该数据出现的次数作为新数组的数据。新数组录入完毕后，依次循环提取出数据不为0的下标，写回原数组，即完成原数组的排序。 <无>

#pragma once

#include<stdlib.h>
#include<stdio.h>
#include<array>

using namespace std;

class BinSort
{
public:
	BinSort(int data[], int size)
	{
		datalist = data;
		datasize = size;
		int maxVal = datalist[0];
		for (int index = 0; index < size; index++)
		{
			if (datalist[index] > maxVal)
				maxVal = datalist[index];
		}//end loop

		binlist = new int[maxVal];
		binsize = maxVal;

		for (int index = 0; index < binsize; index++)
			binlist[index] = 0;

		performBinSort();
	}//end cons

	void performBinSort()
	{
		for (int index = 0; index < datasize; index++)
			binlist[datalist[index] - 1] ++;

		int dataIterator = 0;
		for (int index = 0; index < binsize; index++)
		{
			if (binlist[index] != 0)
			{
				int datanum = binlist[index];
				for (int i = 0; i < datanum; i++)
				{
					datalist[dataIterator] = index + 1;

					////Testing code:
					//printf("Data: %d\n", index);
					//printf("Appeared: %d\n", datanum = binlist[index]);

					dataIterator++;
				}//store data into original data array.
			}//end if: If there are data representing certain original elements.
		}//end for

		printf("\n");
	}//end method: Perform bin sort

	int * getSortedArray()
	{
		return datalist;
	}//Get sorted array

	~BinSort()
	{
		printf("Bin sort finishes!\n");
		system("pause");
	}//end distructor

private:
	int datasize;
	int binsize;
	int * datalist;
	int * binlist;
};//end class

#include "Binsort.h"

void printArray(int * dataarray, int size)
{
	for (int index = 0; index < size; index++)
		printf("%d ", dataarray[index]);
	printf("\n");
}//end method: Print array.

int main()
{
	int intarray[] = { 5, 3, 2, 8, 9, 11, 5, 6, 2, 1, 3, 14 };
	printf("Array before sorting: \n");
	printArray(intarray, 12);
	BinSort sortarray(intarray, 12);
	printf("Array after sorting: \n");
	int * newarray = sortarray.getSortedArray();
	printArray(newarray, 12);
	system("pause");
	return 0;
}