Thread: Insertion Sort and Linked List

Hi, I'm having a hard time getting through this and was wondering if you guys can guide me or lead me in the right direction.

So we have a insertion sort code, something like, a variation

Code:

void stackSort (int n, double * data) {
	double x;
	struct dyArray stk;
	int i = 0;
	
	dyArrayInit(&stk, 3);
	
	while (i < n) {
		x = data[i++];
		while ((!dyArrayIsEmpty(&stk)) && dyArrayTop(&stk) > x) {
			data[--i] = dyArrayTop(&stk);
			dyArrayPop(&stk);
		}
		dyArrayPush(&stk, x);
	}
	
	/* now everything should be on the stack in reverse order */
	while (i > 0) {
		data[--i] = dyArrayTop(&stk);
		dyArrayPop(&stk);
	}
}

or something like pseudocode

Code:

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while A[j] > value do
        begin
            A[j + 1] := A[j];
            A[j] := value;
            j := j - 1;
            if j < 0 then exit while;
        end;
    end;
end;

How would I get that to work with a linked list?

Code:

struct link {
	EleType value;
	
	struct link * next;
	struct link * prev;
};

struct linkedList {
	int size;
	
	struct link * frontSentinel;
	struct link * backSentinel;
};

Also I have methods written out (assuming they work), that add to the front and to the back and remove from the front and the back. that free space up, etc.
Just kinda confused. Thanks

Code:

for n = list; n&& n->value < insert->value; n = n->next
    ...do nothing but loop...
if n == null || n->prev == NULL
    insert->next = root
    root = insert
else
    n->prev->next = insert
    insert->next = n

That looks about right.


Quzah.