вторник, 4 июня 2013 г.

Сортировка списка вставкой

Сортировка довольно медленная О(n в квадрате). Для сортировки большого кол-ва элементов не пойдет. Использовались фиктивные узлы указывающие на головы списков.
Идея  : берем неотсортированный список и по очереди вытаскиваем из него узлы (current). Данный узел помещаем в отсортированный список, который вначале состоит из одного фиктивного узла.

Сортировка списка методом вставки:


void listSort(Node *notSorted, Node *sorted)
{
Node *current; //указывает на узел из неотсортированного списка
Node *nextPosition; //указывает на следующий после текущего
Node *afterWhichInsert; //после которого следует вставка

for (current = notSorted->m_next; current != 0; current = nextPosition)
{
nextPosition = current->m_next; //сохраняем указатель на след. узел
for (afterWhichInsert = sorted; afterWhichInsert->m_next != 0;
                      afterWhichInsert = afterWhichInsert->m_next)
{
if (afterWhichInsert->m_next->m_item > current->m_item)
{
break;
}
}
current->m_next = afterWhichInsert->m_next;
afterWhichInsert->m_next = current;
}
}

main :

int main()
{
srand(time(0));

Node *headNotSorted = new Node(0, 0);  //Фиктивный узел указывает на голову                  неотсортированного списка
Node *headSorted = new Node(0, 0);   //Фиктивный узел указывает на голову отсортированного списка

Node *current = headNotSorted;

for(int i = 1; i < 10; ++i)   //Заполняем список случайными числами
{
current->m_next = new Node(rand()%100, 0);
current = current->m_next;
}
print(headNotSorted->m_next);

listSort(headNotSorted, headSorted);
print(headSorted->m_next);

return 0;
}