fast_sort.cpp

#include <fstream>
#include <ctime>
#include "string.h"
#include "array.h"

using namespace std;

template <typename T>
struct item
{
    int index;
    T data;

    bool operator<(const item& other) const
    {
        #ifdef STABLE
        return data < other.data || (data == other.data && index < other.index);
        #else
        return data < other.data;
        #endif

    }

    bool operator>(const item& other) const
    {
        #ifdef STABLE
        return data > other.data || (data == other.data && index > other.index);
        #else
        return data < other.data;
        #endif

    }
};

/*istream& operator>>(istream& in, item& item)
{   in >> item.data;
    return in;
}
ostream& operator<<(ostream& out, item& item)
{ out << "[" << item.index << "] " << item.data;
    return out;
}
*/
template <typename T>
istream& operator>>(istream& in, item<T>& item)
{
    in >> item.data;
    return in;
}

template <typename T>
ostream& operator<<(ostream& out, const item<T>& item)
{
    out << "[" << item.index << "] " << item.data;
    return out;
}

template <typename T>
void swap(T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;
}


template <typename T>
int partition(Array<T>& arr, int low, int high, bool (*cmp)(T a, T b))
{
    T pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true)
    {

        do
        {
            i++;
        } while ((cmp(arr[i], pivot)));

        do
        {
            j--;
        } while ((cmp(pivot, arr[j])));


        if (i >= j)
        {
            return j;
        }

        ::swap(arr[i], arr[j]);
    }
}

template <typename T>
void quicksort(Array<T>& arr, int low, int high, bool (*cmp)(T a, T b))
{
    if (low < high)
    {
        int pi = partition(arr, low, high, cmp);
        quicksort(arr, low, pi, cmp);
        quicksort(arr, pi + 1, high, cmp);
    }
}

template <typename T>
bool Asc(T a, T b)
{
    return a < b;
}

template <typename T>
bool Desc(T a, T b)
{
    return a > b;
}

template <typename T>
void sort(Array<T>& arr, bool asc)
{
    quicksort(arr, 0, arr.size() - 1, asc ? Asc<T> : Desc<T> );
}

template <typename T>
Array<T> load_array(const String& filename)
{
    Array<T> arr;
    ifstream in(filename.str);
    if (!in)
    {
        cerr << "Error: File not found - " << filename.str << endl;
        exit(1);
    }
    T value;
    while (in >> value.data)
    {
        if (in.eof())
        {
            break;
        }
       value.index = arr.size();
        arr.append(value);
    }
    return arr;
}

template <typename T>
Array<item<T>> load_array_pos(const String& posfilename)
{
    Array<item<T>> arr;
    ifstream in(posfilename.str);
    if (!in)
    {
        cerr << "Error: File not found - " << posfilename.str << endl;
        exit(1);
    }

    T value;
    int index = 0;
    while (in >> value)
    {
        if (in.eof())
        {
            break;
        }
        item<T> newItem;
        newItem.data = value;
        newItem.index = index++;
        arr.append(newItem);
    }

    return arr;
}


template <typename T>
void print_array(const Array<T>& arr)
{
    for (int i = 0; i < arr.size(); i++)
    {
        if (i > 0) cout << " ";
        cout << arr[i];
    }
    cout << endl;
}

template <typename T>
bool is_sorted(const Array<T>& arr, bool asc)
{
    for (int i = 1; i < arr.size(); i++)
    {
        if ((asc && arr[i] < arr[i - 1]) || (!asc && arr[i] > arr[i - 1]))
        {
            return false;
        }
        if (arr[i].data == arr[i - 1].data && arr[i].index < arr[i - 1].index)
        {
            cout << "По индексу:" << arr[i].data << "  Лежит:" << arr[i-1] << "  Должно:" << arr[i] << endl;
            return false;
        }
    }
    return true;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        cerr << "Usage: fastsort file [asc|desc] [-o] [-v]" << endl;
        return 1;
    }

    String posfilename = argv[1];
    bool asc = true;
    bool verbose = false;
    String outputFile;

    for (int i = 2; i < argc; i++)
    {
        if (String(argv[i]) == "desc")
        {
            asc = false;
        } else if (String(argv[i]) == "asc")
        {
            asc = true;
        } else if (String(argv[i]) == "-o" && i + 1 < argc)
        {
            outputFile = argv[++i];
        } else if (String(argv[i]) == "-v")
        {
            verbose = true;
        } else
        {
            cerr << "Error: Unknown option - " << argv[i] << endl;
            return 1;
        }
    }

    clock_t startTime = clock();
    Array<item<int>> arr = load_array_pos<int>(posfilename);
    clock_t loadTime = clock() - startTime;

    startTime = clock();
    sort(arr, asc);
    clock_t sortTime = clock() - startTime;

    if (outputFile.length() > 0)
    {
        ofstream out(outputFile.str);
        if (!out)
        {
            cerr << "Error: Failed to open output file - " << outputFile.str << endl;
            return 1;
        }
        for (int i = 0; i < arr.size(); i++)
        {
            out << arr[i].data << " ";
        }
        out << endl;
    } else
    {
        print_array(arr);
    }

    if (verbose)
    {
        cout << "Load time: " << static_cast<double>(loadTime) / CLOCKS_PER_SEC << " sec" << endl;
        cout << "Sort time: " << static_cast<double>(sortTime) / CLOCKS_PER_SEC << " sec" << endl;
        cout << "Memory used: " << arr.size() * sizeof(item<int>) / 1024.0 << " KB" << endl;
        //cout << "Memory used: " << arr.size() * sizeof(item) / 1024.0 << " KB" << endl;
    }

    if (!is_sorted(arr, asc))
    {
        print_array(arr);
        return 1;
    }

    return 0;
}