Сортировка односвязного списка с использованием перегрузки индекса

Я не могу понять, как получить мой односвязный список в мой метод сортировки. Я должен перегрузить индекс, чтобы иметь доступ к различным частям моего списка. Проблема, с которой я сталкиваюсь, заключается в том, чтобы выяснить, как изменить этот список с помощью функции сортировки.

template <typename E> 
class SNode {
private:
    E elem;
    SNode<E>* next;
    friend class SLinkedList<E>;
    template <typename E>
    friend ostream& operator <<(ostream& out, SLinkedList<E>& v);
};

template <typename E> 
class SLinkedList {
 public:
    SLinkedList();
    ~SLinkedList();
    bool empty() const;
    const E& front() const;
    void addFront(const E& e);
    void removeFront();
    int getSize();
    SNode<E>* getHead();
    void sort();
    void printDetails() const;

    //overload

    E& operator[] (const int index);
    const E& operator[] (const int index) const;

private:
    SNode<E>* head;
    int size;
 };
    template <typename E>
    E& SLinkedList<E>::operator [](const int index) {
    SNode<E>* temp = head;

    for (int i = 0; i < index; i++) {
        temp = temp->next;
    }
    E out = temp->elem;
    return out;
    }

template <typename E>
const E& SLinkedList<E>::operator [](const int index) const {
    SNode<E>* temp = head;

    for (int i = 0; i < index; i++) {
        temp = temp->next;
    }    
    E out = temp->elem;
    return out;
}

template <typename E>
void SLinkedList<E>::sort() {
    for (int i = 1; i < getSize(); ++i) {
        E curr = (*this)[i];
        int j = i - 1;
        while (j >= 0 && (*this)[j] > curr); {
            E temp = (*this)[i];
            this->elem = (*this)[j];
            this[j] = temp;
            j = j - 1;
        }
        (*this)[j + 1] = curr;

    }
}

void main() {
SLinkedList<float> lst;

int lstElems = 10;
srand(time(NULL));
for (int i = 0; i < lstElems; i++) {
    lst.addFront(randGen());
}
cout << "Unsorted list: " << lst << endl;
lst.printDetails();
cout << "TEST SINGLE LIST ELEMENT: " << lst[1] << endl;
lst.sort();
cout << "Sorted list: " << lst << endl;



system("pause");

}


person Richard Rasmussen    schedule 19.10.2015    source источник
comment
Доступ к списку оператором [] - это O (i), где i будет доступной позицией; это ограничивает производительность любого метода сортировки как минимум O (n ^ 2), а может быть и хуже. Оператор [] работает для массивов, потому что доступ к ним равен O(1), а со списком — нет. Вы должны разработать свой метод сортировки, не думая о позициях. Подсказка: подумайте о сортировке вставками для квадратичного алгоритма или о стратегии «разделяй/властвуй» для получения O (n log n) -быстрой сортировки или сортировки слиянием-. Любопытно, что алгоритмы «разделяй/властвуй» проще для сортировки списков, чем для массивов. Удачи   -  person lrleon    schedule 19.10.2015
comment
Я согласен, что это действительно глупый способ сортировки списка, но это то, что требуется для задания.   -  person Richard Rasmussen    schedule 19.10.2015


Ответы (1)


person    schedule
comment
Проблема заключается в том, что мой метод сортировки фактически сортирует список - person Richard Rasmussen; 19.10.2015