Re: In-place list manipulation

On Nov 23, 1:52 pm, "jehugalea...@xxxxxxxxx" <jehugalea...@xxxxxxxxx>
wrote:
On Nov 22, 6:30 am, "Aki Tuomi" <cmo...@xxxxxxxxxxx> wrote:





When doing mergesort in place, I have ran into a following problem:

How to perform in-place interleave during merge without need of auxilliary
list or array?

I have two sets of indexes: a.start, a.stop and b.start and b.stop. These
contain start and stop indexes in the list where the data is. My question
is, how do I do merge the two into the list in-place?

Example:

List = {1,3,2,5,4,6,7,8,9}

a.start = 1
a.stop = 2

b.start = 3
b.stop = 4

a = {3,2}
b = {5,4}

merge(a,b,List)

List = {1,2,3,4,5,6,7,8,9}

I have solved this now by copying the two segments into temporary arrays and
then copy data back from there, but it does not really feel right. Any
ideas?

Aki Tuomi

With linked lists, auxilary lists are inexpensive. Essentially, you
Splice elements from one list into the other. The splicing simply
changes pointers, so no data is actually moved. Simply splice into the
auxilary until it contains elements of both lists, then splice the
result into one of the originals.


Hmmm.... But here is an implementation.

Sorts a one-million integer list in about 1 second on my fairly old
machine.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s {
int val;
struct node_s *next;
} NODE;

void print_list(NODE *p)
{
for ( ; p; p = p->next) printf("%d ", p->val);
printf("\n");
}

/* cut lst in half and return head of second part */
NODE *split(NODE *lst)
{
NODE *q, *p;

q = lst;
p = lst->next;
while (p) {
p = p->next;
if (!p) break;
p = p->next;
q = q->next;
}
p = q->next;
q->next = NULL;
return p;
}

/* return merge of lists a and b */
NODE *merge(NODE *a, NODE *b)
{
NODE *hd, *tl, *p;

hd = tl = NULL;
while (a || b) {
if (!b || (a && a->val <= b->val)) {
p = a;
a = a->next;
}
else {
p = b;
b = b->next;
}
if (tl) {
tl->next = p;
tl = p;
}
else
hd = tl = p;
}
return hd;
}

NODE *sort(NODE *a)
{
NODE *b;

if (!a || !a->next) return a;
b = split(a);
return merge(sort(a), sort(b));
}

int main(void)
{
int i;
NODE *p, *lst = NULL;

for (i = 0; i < 1000000; i++) {
p = malloc(sizeof *p);
p->val = rand();
p->next = lst;
lst = p;
}
print_list(sort(lst));
return 0;
}
.

Relevant Pages