Here's a snippet to help anyone who wants to do a sorted linked list:
[size=9]

InsertionSort PROC USES ebx esi edi headPtr:DWORD

mov esi, headPtr
mov edi, (CarInfo PTR [esi]).ptNext
mov (CarInfo PTR [esi]).ptNext, NULL

@@SearchAndInsert:

mov edx, esi
mov eax, (CarInfo PTR [edi]).cID
mov ebx, (CarInfo PTR [edi]).ptNext

@@SearchInner:

cmp (CarInfo PTR [edx]).cID, eax
jbe @@SkipInsert
cmp edx, esi
jne @@MiddleInsertion
mov (CarInfo PTR [edx]).ptPrev, edi
mov (CarInfo PTR [edi]).ptPrev, NULL
mov (CarInfo PTR [edi]).ptNext, edx
mov esi, edi
jmp @@ScanForward

@@MiddleInsertion:

push edi
push edi
mov ecx, (CarInfo PTR [edx]).ptPrev
push ecx
push ecx
push edx
pop (CarInfo PTR [edi]).ptNext
pop (CarInfo PTR [edi]).ptPrev
pop ecx
pop (CarInfo PTR [ecx]).ptNext
pop (CarInfo PTR [edx]).ptPrev
jmp @@ScanForward

@@SkipInsert:

mov ecx, edx
mov edx, (CarInfo PTR [edx]).ptNext
or edx, edx
jnz @@SearchInner
mov (CarInfo PTR [ecx]).ptNext, edi
mov (CarInfo PTR [edi]).ptNext, NULL
mov (CarInfo PTR [edi]).ptPrev, ecx

@@ScanForward:

mov edi, ebx
or edi, edi
jnz @@SearchAndInsert
mov eax, esi

ret

InsertionSort ENDP[/size]
I don't know if this is an insertion sort but it sort-of work like insertion sort. The only difference is that it will not just insert itself automatically like the other insertion sort methods shown mostly out there on the net but it will find a suitable spot where it will insert and swap memory pointers.

Requirements: A doubly linked list
Parameter: The head pointer of the current linked list
Return Value: In EAX, the new head pointer
Notes: Replace the following with your own:
CarInfo == with the name of your structure
cID == replace this with the structure field you want to compare.
ptNext == the name of your next pointer in the structure field
ptPrev == the name of your previous pointer in the structure field

It's the programmer's responsibility to ensure a perfect doubly linked list. I mean the doubly linked list should have no problems with its prev and next pointers. To test a perfect doubly linked list try printing it starting at the head node going to the tail and vice versa.

This sorts in ascending order.

Optimizations: A LOT!!! but I'll leave this up to you guys, since I have more projects to finish. :grin: My spring break sucks!!! :grin:

Its best running time is O(n) - Ha! Beat That. Especially if the data is sorted in descending order(9 8 7 6...). Its worst is I don't know but this one will perform poorly if the data is already sorted in ascending order(1 2 3 4 5 ....).
Posted on 2002-03-28 00:57:55 by stryker
I updated it quite a bit to support doubly circular linked list.
[size=9]

InsertionSort PROC USES ebx esi edi headPtr:DWORD

LOCAL tailPtr :DWORD

mov esi, headPtr
mov tailPtr, esi

mov edi, (CarInfo PTR [esi]).ptNext
mov (CarInfo PTR [esi]).ptNext, NULL

@@SearchAndInsert:

mov edx, esi
mov eax, (CarInfo PTR [edi]).cID
mov ebx, (CarInfo PTR [edi]).ptNext

@@SearchInner:

cmp (CarInfo PTR [edx]).cID, eax
jbe @@SkipInsert

cmp edx, esi
jne @@MiddleInsertion

mov (CarInfo PTR [edx]).ptPrev, edi
mov (CarInfo PTR [edi]).ptPrev, NULL
mov (CarInfo PTR [edi]).ptNext, edx
mov esi, edi
jmp @@ScanForward

@@MiddleInsertion:

push edi
push edi
mov ecx, (CarInfo PTR [edx]).ptPrev
push ecx
push ecx
push edx
pop (CarInfo PTR [edi]).ptNext
pop (CarInfo PTR [edi]).ptPrev
pop ecx
pop (CarInfo PTR [ecx]).ptNext
pop (CarInfo PTR [edx]).ptPrev

jmp @@ScanForward

@@SkipInsert:

mov ecx, edx
mov edx, (CarInfo PTR [edx]).ptNext
or edx, edx
jnz @@SearchInner

mov (CarInfo PTR [ecx]).ptNext, edi
mov (CarInfo PTR [edi]).ptNext, NULL
mov (CarInfo PTR [edi]).ptPrev, ecx
mov tailPtr, edi

@@ScanForward:

mov edi, ebx
cmp edi, headPtr
jne @@SearchAndInsert

mov eax, tailPtr
mov (CarInfo PTR [eax]).ptNext, esi
mov (CarInfo PTR [esi]).ptPrev, eax

mov eax, esi

ret

InsertionSort ENDP[size=9][/size]
This sorts the DCLL in ascending order. And don't forget that you must ensure it must be a perfect doubly circular linked list before you use this.

To test your DCLL, try printing from head to tail twice in continous flow and do the same thing from tail to head. The output should be the reverse of the other.

This snippet was tested on 3 cases of a doubly circular linked list:

1. Already sorted in ascending
2. Already sorted in descending
3. Unsorted

Everything came out perfectly as it should be. It's best and worst cases are the same as the one above.

An app will be released soon, together with the complete binary trees examples.

Have Fun!!! :grin:
Posted on 2002-04-02 23:40:49 by stryker