у меня есть односвязный список:

мне надо реализовать рекурсивную быструю сортировку. представляю себе это так:

допустим у меня есть текущий элемент списка, значение которого меньше опорного, следовательно, я должен вставить его в начало, когда я буду вставлять элемент перед опорным я выделю динамическую память,  скопирую значение текущего элемента в новый,  потом текущий элемент удалю и поставлю указатель Llink на новый элемент. Затем передам указатель на дальнейшее разбиение левого "списка". То есть мне надо будет сохранить значение опорного элемента, и левую половину списка разбивать до опорного? так будет очень долго, нельзя ли как-нибудь по другому реализовать? без вставки и удаления.

Это сообщение отредактировал(а) Luyan - 9.12.2009, 20:57

не проще ли будет просто  поменять data (тем более что int), не трогая в остальном Node ?

вот список:  ( p - pivot, h - head)
5    8    10    4    13    2
^    ^
p    h

дошёл до 4

5    8    10    4    13    2
^                  ^
p                   h

поменял значения:

4    8    10    5    13    2
^                 ^
p                  h

дальше так: Llink = pivot; pivot = head; и через дополнительный указатель смешу head 
4    8    10    5    13    2
^                  ^    ^
L                   p    h

двигаюсь:
4    8    10    5    13    2
^                 ^            ^
L                  p             h

не получается. 10 и 13 уже не там.
4    8    10    2    13    5
^                  ^
L                   p

Добавлено через 5 минут и 39 секунд
кажеться я вас не так понял...

Это сообщение отредактировал(а) Luyan - 10.12.2009, 00:12

имелось ввиду типа этого :

однако для Вашего типа сортировки не подходит.. так как нельзя вставить в середину, можно только поменять.
Но для вставки тоже совсем необязательно выделять дополнительно память- можно поменять лишь откорректировать указатели next.


Это сообщение отредактировал(а) mes - 10.12.2009, 00:25

  , можете объяснить как?

вот псевдокодом, набросал не проверяя...



Это сообщение отредактировал(а) mes - 10.12.2009, 01:29

то есть сначала идёт prevfrom, потом from? to - после которого буду вставлять, для первого случая == head, после вставки его смещаю?

ничего не происходит, что не так? может ввести указатель на указатель, допустим так, псевдокод:


Добавлено через 5 минут и 34 секунды
только как потом связать...

Это сообщение отредактировал(а) Luyan - 11.12.2009, 22:11

удалось, реализовал своим способом. mes, спасибо за подкунутую идею   

Это сообщение отредактировал(а) Luyan - 12.12.2009, 16:50