4

#include <iostream>
#include <ctime>

using namespace std;

class LinkedList
{
private:
    struct ListItem
    {
        int current;
        ListItem *nextItem, *prevItem;
    };

    ListItem *Head, *last;
    int size = 0;

    void quickSort(int left, int right)
    {
        int pivot;
        int l_hold = left;
        int r_hold = right;
        pivot = this->get(left);
        while (left < right)
        {
            while ((this->get(right) >= pivot) && (left < right))
                right--;
            if (left != right)
            {
                this->get(left) = this->get(right);
                left++;
            }
            while ((this->get(left) <= pivot) && (left < right))
                left++;
            if (left != right)
            {
                this->get(right) = this->get(left);
                right--;
            }
        }
        this->get(left) = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot)
            quickSort(left, pivot - 1);
        if (right > pivot)
            quickSort(pivot + 1, right);
    }

public:
    ~LinkedList()
    {
        while (Head)
        {
            last = Head->nextItem;
            delete Head;
            Head = last;
        }
    }

    int& get(int x) {
        if (x < size) {
            int *value;
            ListItem *item = Head;
            for (int i = 0; i < x; ++i) {
                item = item->nextItem;
            }
            return item->current;
        }
        else {
            throw "Out of range";
        }
    }

    void add(int x)
    {
        size++;
        ListItem *temp = new ListItem;
        temp->nextItem = NULL;
        temp->current = x;

        if (Head != NULL)
        {
            temp->prevItem = last;
            last->nextItem = temp;
            last = temp;
        }
        else
        {
            temp->prevItem = NULL;
            Head = last = temp;
        }
    }

    void show()
    {
        ListItem *temp = last;

        while (temp != NULL)
        {
            temp = Head;
            while (temp != NULL)
            {
                cout << temp->current << " ";
                temp = temp->nextItem;
            }
            cout << "\n";
        }
    }

    void quickSorting() {
        if (size > 1)
            quickSort(0, size - 1);
    }
};

LinkedList *getRandomList(int size) {
    LinkedList *list = new LinkedList();
    for (int i = 0; i < size; ++i) {
        list->add(rand());
    }
    return list;
}

LinkedList *getAlmostRandomList(int size) {
    LinkedList *list = new LinkedList();
    int pivot = rand() % (size - 1);
    for (int i = 0; i < pivot; ++i) {
        list->add(rand());
    }
    list->quickSorting();
    for (int i = pivot; i < size; i++) {
        list->add(rand());
    }
    return list;
}

LinkedList *getReverseList(int size) {
    LinkedList *list = new LinkedList();
    for (int i = 0; i < size; ++i) {
        list->add(rand());
    }
    list->quickSorting();

    LinkedList *reverseList = new LinkedList();
    for (int i = size - 1; i >= 0; --i) {
        reverseList->add(list->get(i));
    }

    return reverseList;
}

int* getRandomTimes() {
    int *times = new int[3];
    LinkedList *list;

    list = getRandomList(1000);
    int startTime = clock();
    list->quickSorting();
    int endTime = clock();
    times[0] = endTime - startTime;

    list = getRandomList(5000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[1] = endTime - startTime;

    list = getRandomList(10000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[2] = endTime - startTime;

    return times;
}

int* getAlmostTimes() {
    int *times = new int[3];
    LinkedList *list;

    list = getAlmostRandomList(1000);
    int startTime = clock();
    list->quickSorting();
    int endTime = clock();
    times[0] = endTime - startTime;

    list = getAlmostRandomList(5000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[1] = endTime - startTime;

    list = getAlmostRandomList(10000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[2] = endTime - startTime;

    return times;
}

int* getReverseTimes() {
    int *times = new int[3];
    LinkedList *list;

    list = getReverseList(1000);
    int startTime = clock();
    list->quickSorting();
    int endTime = clock();
    times[0] = endTime - startTime;

    list = getReverseList(5000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[1] = endTime - startTime;

    list = getReverseList(10000);
    startTime = clock();
    list->quickSorting();
    endTime = clock();
    times[2] = endTime - startTime;

    return times;
}

void printTimes(int *times) {
    cout << "1000 items  --> " << times[0] << "ms" << endl;
    cout << "5000 items  --> " << times[1] << "ms" << endl;
    cout << "10000 items --> " << times[2] << "ms" << endl;
}

int main() {
    int *times = getRandomTimes();
    cout << "<--Random sort-->" << endl;
    printTimes(times);
    cout << endl;

    times = getAlmostTimes();
    cout << "<--Almost random sort-->" << endl;
    printTimes(times);
    cout << endl;

    times = getReverseTimes();
    cout << "<--Reverse sort-->" << endl;
    printTimes(times);
    cout << endl;

    delete times;
    system("pause");
    return 0;
}