Witam, mam problem z posortowaniem listy dwukierunkowej metodą quicksort. Problem polega na tym, że funkcja usuwa mi elementy mniejsze od pierwszego elementu listy, reszte natomiast normalnie sortuje i nie mogę dojść w czym problem. Zamieszczam kod funkcji do sortowania, partycjonowania i usuwania elementów:
void Sort(lista *head)
{
lista *Lw = new lista, *Pw = new lista;
Lw->Value = NULL;
Lw->prev = NULL;
Lw->next = head;
if (Lw->next)
Lw->next->prev = Lw;
Pw->Value = NULL;
Pw->next = NULL;
Pw->prev = GetTail(head);
if (Pw->prev)
Pw->prev->next = Pw;
Partition(Lw, Pw);
Delete(Lw, Lw);
Delete(head, Pw);
}
void Partition(lista *Lw, lista *Pw)
{
lista *pivot, *i, *j;
pivot = Lw->next;
i = pivot->next;
if (i != Pw)
{
do
{
j = i;
i = i->next;
if (j->Value < pivot->Value)
{
j->prev->next = j->next;
j->next->prev = j->prev;
j->next = pivot;
j->prev = pivot->prev;
pivot->prev = j;
j->prev->next = j;
}
} while (i != Pw);
if (Lw->next != pivot)
Partition(Lw, pivot);
if (pivot->next != Pw)
Partition(pivot, Pw);
}
}
lista *Delete(lista *head, lista *to_delete)
{
if (to_delete->prev)
to_delete->prev->next = to_delete->next;
else
head = to_delete->next;
if (to_delete->next)
to_delete->next->prev = to_delete->prev;
else
{
if (to_delete->prev == NULL)
head = NULL;
else
to_delete->prev->next = NULL;
}
delete to_delete;
return head;
}