I've written bucket sort, to read a list of numbers from a file, sort them, then write the sorted list to a new file. My program runs through the process just as it should, but whenever a bucket is completely sorted, it doesn't save the changes in the bucket. My file consisted of these numbers:
150 221 19 60 42
11 20 94 65
Here is my code (It is a little long, I apologize):
// Bucket Sort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;
// Functions for file I/O
string getFileName(string);
string getExtension(string);
vector<int> readFile(string);
void saveFile(vector<int>, string);
void printCollection(vector<int>);
// Functions for the sort
int getDigits(int);
vector<int> bucketSort(vector<int>&, int);
int getValueAtDigit(int, int);
int getHighestValue(vector<int>);
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> collection;
string fullFile = "";
string fileName = "";
string extension = "";
string newFileName = "";
cout << "Enter a file name to read data from: ";
cin >> fullFile;
// gets the file naem and extension
fileName = getFileName(fullFile);
extension = getExtension(fullFile);
// creates a new file name for the sorted collection
newFileName = fileName + "-sorted" + extension;
// read the file, put it's contents in a vector
collection = readFile(fullFile);
cout << "Un-Sorted: " << endl << endl;
printCollection(collection);
cout << endl;
collection = bucketSort(collection, getDigits(getHighestValue(collection)));
cout << "Sorted: " << endl;
cout << endl;
printCollection(collection);
cout << endl;
//saveFile(collection, newFileName);
system("pause");
return 0;
}
int getHighestValue(vector<int> data)
{
int max = 0;
for (int i = 0; i < data.size(); i++)
{
if (data[i] > max)
max = data[i];
}
return max;
}
int getDigits(int number)
{
int digits = 0;
while (number > 0)
{
number /= 10;
digits++;
}
return digits;
}
int getValueAtDigit (int number, int digit)
{
int result = 0;
int divisor = 1;
if (digit == 1)
{
result = number % 10;
}
else
{
for (int i = 0; i < digit - 1; i++)
{
divisor *= 10;
}
result = number / divisor;
}
return result;
}
vector<int> bucketSort(vector<int> &data, int digit)
{
if (digit == 0 || data.size() == 1)
return data;
// -Create 10 buckets
// -Get the maximum value
// -Get the number of digits in that number
// -Place each element in bucket 1-10
// according to it's value at that digit place
// -Loop through each bucket with the next digit
vector<vector<int>> buckets;
vector<int> tmp;
int maxValue = 0;
int value = 0;
int elementCount = 0;
// add the buckets to the vector
for (int i = 0; i < 10; i++)
buckets.push_back(tmp);
maxValue = getHighestValue(data);
// put each element in the a bucket based
// on it's digit value at the highest digit
for (int i = 0; i < data.size(); i++)
{
value = getValueAtDigit(data[i], digit);
buckets[value].push_back(data[i]);
}
data.clear();
// put the buckets back into the original vector
for (int i = 0; i < buckets.size(); i++)
{
elementCount = 0;
while (elementCount < buckets[i].size())
{
data.push_back(buckets[i].at(elementCount));
elementCount++;
}
}
for (int i = 0; i < buckets.size(); i++)
{
// if the bucket's size is 1 or less, it's sorted
if (buckets[i].size() <= 0)
continue;
else
{
buckets[i] = bucketSort(buckets[i], digit - 1);
}
}
return data;
}
void printCollection(vector<int> data)
{
for (int i = 0; i < data.size(); i++)
{
if (i % 4 == 0 && i != 0)
cout << data[i] << endl;
else
cout << data[i] << "\t";
}
}
void saveFile(vector<int> data, string fileName)
{
ofstream newFile(fileName, ios::trunc);
stringstream tmp;
// insert data from a vector into a stringstream
for (int i = 0; i < data.size(); i++)
{
// write five numbers to each line
if (i % 4 == 0 && i != 0)
tmp << data[i] << "\n";
else
tmp << data[i] << " ";
}
// insert the stringstream into the file
newFile << tmp.str();
}
vector<int> readFile(string fileName)
{
vector<int> data;
// placeholder vars for getline()
string placeHolder = "";
string otherPlaceHolder = "";
ifstream file(fileName);
stringstream ss;
if (file.is_open())
{
// read each line of the file
while (getline(file, placeHolder, '\n'))
{
// insert the line into a stream
ss << placeHolder;
// get each number in the file delimited by a space
while (getline(ss, otherPlaceHolder, ' '))
{
// insert into vector
data.push_back(atoi(otherPlaceHolder.c_str()));
}
// clear the stream for the next line
ss.clear();
}
}
return data;
}
string getFileName(string file)
{
string tmp = "";
int counter = 0;
int endPos = 0;
for (int i = file.length() - 1; i >= 0; i--)
{
if (file[i] == '.')
endPos = i;
}
while (counter < endPos)
{
tmp += file[counter];
counter++;
}
return tmp;
}
string getExtension(string file)
{
string tmp = "";
int startPos = 0;
for (int i = 0; i < file.length(); i++)
{
if (file[i] == '.')
startPos = i;
}
while (startPos < file.length())
{
tmp += file[startPos];
startPos++;
}
return tmp;
}
So if anyone can help me out with this or give me advice on things that could be better in my program, that'd be awesome. Thank you for your time!
Oh, and this is for a school assignment. I was instructed to use the recursive method for bucket sort and to use vectors.
