Quicksort Throws Stack Overflow error

Question

Okay, so my entire program is shown below. For some reason, when the partition function is called, it is throwing a stack overflow error. I have poured over the code and searched for help. You fine programmers are my last hope. Everything else works fine, or at least as well as it needs to. I'd appreciate it if you could look at the Quicksort and the partition functions for me and see if you can figure out where I messed up.

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <vector>
    #include <time.h>
    #include <stdio.h>
    #include <dos.h>

using namespace std;

vector<int> DataIn(ifstream&);

void quickSort(int, int, vector<int>&, int);

int partition(vector<int>& list, int start, int end)
{
    int pivot = list[start];
    int index = start;

    for (int i = start + 1; i < end; i++)
    {
        if (list[i] <= pivot)
        {
            swap(list[index], list[i]);
        }
    }

    index++;

    if (index != end)
    {
        swap(list[index], list[start]);
    }
    return index;
}

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

int main()
{
    int repeat = 0;
    int fileCount = 1;

    while (repeat == 0)
    {

        int loadFail = NULL;

        cout << "\nWhat is the file name: ";

        string fileName;
        cin >> fileName;

        ifstream fileIn(fileName);

        do
        {
            if (fileIn.fail())
            {
                loadFail = 1;
                cout << "\nUnable to open file. Please try again:";

                cout << "\nWhat is the file name: ";

                cin >> fileName;
                ifstream fileIn(fileName);

                if (fileIn.good())
                {
                    loadFail = 0;
                }
            }
            else
            {
                loadFail = 0;
            }
        } while (loadFail == 1);

        vector<int> fileData;

        fileData = DataIn(fileIn);

        int fileLength = fileData.size();

        void quickTime = quickSort(0, fileLength - 1, fileData, fileCount);


    return 0;
};

vector<int> DataIn(ifstream& read)
{
    vector<int> data;
    int dataLine;

    while (!read.eof())
    {
        read >> dataLine;
        read.ignore();
        data.push_back(dataLine);
    }

    return data;
}

void quickSort(int begin, int end, vector<int>& list, int fileNum)
{    
    int mid = 0;

    if (end > begin)
    {       
        mid = partition(list, begin, end);
        quickSort(begin, mid, list, fileNum);
        quickSort(mid + 1, end, list, fileNum);
    }

    return elapsed_time;    
}

Answer 1

You have a few major issues in your posted code.

1. You are trying to return a value in void function (quickSort). Also I don't see where you declared that variable.

2. You are declaring a type void variable, which is wrong. A void function return void, that means that it doesn't return anything.

3. You have a missing bracket at the end of the main() function.

4. Your while loop will never stop, because repeat is always equal with 0.

5. In your quick sort function, in the first recursive call there should be mid-1

6. Your partitioning function logic is wrong

Also filenum variable is not used anywhere.

Here is a modified version of your code, that does work.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <time.h>
#include <stdio.h>
#include <dos.h>

using namespace std;

vector<int> DataIn(ifstream&);

void quickSort(int, int, vector<int>&);

int partition(vector<int>& arr, int left, int right)
{
    int pivot = arr[left];
    while (left != right)
    {
        if (arr[left] > arr[right])
        {
            swap(arr[left], arr[right]);
        }
        if (pivot == arr[left])
            right--;
        else 
            left++;
    }
    return left;
}

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

int main()
{
    int repeat = 0;
    int fileCount = 1;

        int loadFail = NULL;

        cout << "\nWhat is the file name: ";

        string fileName;
        cin >> fileName;

        ifstream fileIn(fileName);

        do
        {
            if (fileIn.fail())
            {
                loadFail = 1;
                cout << "\nUnable to open file. Please try again:";

                cout << "\nWhat is the file name: ";

                cin >> fileName;
                ifstream fileIn(fileName);

                if (fileIn.good())
                {
                    loadFail = 0;
                }
            }
            else
            {
                loadFail = 0;
            }
        } while (loadFail == 1);

        vector<int> fileData;

        fileData = DataIn(fileIn);

        int fileLength = fileData.size();

        quickSort(0, fileLength - 1, fileData);


        return 0;
}

    vector<int> DataIn(ifstream& read)
    {
        vector<int> data;
        int dataLine;

        while (!read.eof())
        {
            read >> dataLine;
            read.ignore();
            data.push_back(dataLine);
        }

        return data;
    }

    void quickSort(int begin, int end, vector<int>& list)
    {
        int mid = 0;

        if (end > begin)
        {
            mid = partition(list, begin, end);
            quickSort(begin, mid-1, list);
            quickSort(mid + 1, end, list);
        }
    }