no_stable_fast_sort

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

using namespace std;

struct item
{
    int index;
    int data;

    bool operator<(const item& other) const
    {
        return data < other.data;// || (data == other.data && index < other.index);
    }

    bool operator>(const item& other) const
    {
        return data > other.data;// || (data == other.data && index > other.index);
    }
};

istream& operator>>(std::istream& in, item& item)
{   in >> item.data;
    return in;
}
ostream& operator<<(std::ostream& out, item 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)
    {
        value.index = arr.size();
        arr.append(value);
    }

    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 filename = 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> arr = load_array<item>(filename);
    clock_t loadTime = clock() - startTime;

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


    if (!is_sorted(arr, asc))
    {
        print_array(arr);
        return 1;
    }
    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) / 1024.0 << " KB" << endl;
    }

    return 0;
}