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.

Edited 3 Years Ago by rfrapp

Write it out first in pseudo-code - 300 (almost) lines of code is too much to analyze quickly. That will help you determine if you are doing what you think. Then write the code to implement the algorithm/pseudo-code.

Most of the code isn't the sort. You can tell that by just looking at the function names...

This article has been dead for over six months. Start a new discussion instead.