help with sorting

[CBFalconer]

Simon Bachmann wrote:

I would do something like this:

-you need two counters(ia ib):
one for a, one for b. their initial value is na respecively nb
-use this counters to compare the respective elements
of the two arrays
-copy the greather to the last (empty) element of b
-decrease the counter ia OR ib (ia if a[ia] > b[ib], ib otherwise)
-go on "filling up" b from the last element
towards the first, comparing a[ia] b[ib]

This way you need no additional memory allocation,
and work will be done with exactly na+nb passages.

I was about to complain that you would need to reserve
storage for ia and ib, but of course you can use na and nb,
which you get for free. Very neat.

I very much prefer the "pointer to element, size_t"
sorting function interface, which I got from Dann Corbit,
over the interface where everything is int and pointers to int,
for two reasons: 1 pedagogy, 2 practicality.

From a sorting algorithm point of view,
the objects which are used for book keeping inside the function,
like your ia and ib above, are conceptually,
completely different from the array elements which are also integers.

.... snip code etc. ...

Here is my version of the algorithm. The actual merge is 4 lines
of code. It is O(N), where N is the size of the merged array.

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

/* Simulating arrays to mergesort in place with strings */
/* blanks represent empty locations. The strlen represents */
/* the actual array capacity, which is fixed */

char aitem[] = "abde ";
char bitem[] = "acegjmpr ";
char citem[] = "acegjmpr ";
char ditem[] = "acegjmpr ";

#define UNUSED ' '

/* ----------------- */

void showitem(char *s, int index)
{
if (index >= 0) printf("[%d] ", index);
printf("\"%s\"\n", s);
} /* showitem */

/* ----------------- */

void merge(char *new, char* into)
{
int intosize, intolgh, newlgh;

/* extract parameters */
intosize = strlen(into);
intolgh = strchr(into, UNUSED) - into;
newlgh = strchr(new, UNUSED) - new;

/* validate space available */
if (intosize < (intolgh + newlgh)) return; /* No room */
if (intosize > (intolgh + newlgh))
intosize = intolgh + newlgh;

/* The actual merge operation */
while (newlgh && (intosize > intolgh)) {
if (into[intolgh-1] > new[newlgh-1])
into[--intosize] = into[--intolgh];
else into[--intosize] = new[--newlgh];
}
} /* merge */

/* ----------------- */

int main(void)
{
showitem(aitem, -1); showitem(bitem, -1);
merge(aitem, /* into */ bitem);
showitem(bitem, -1);
showitem(aitem, -1); showitem(citem, -1);
merge(aitem, /* into */ citem);
showitem(citem, -1);
showitem(aitem, -1); showitem(ditem, -1);
merge(aitem, /* into */ ditem);
showitem(ditem, -1);
return 0;
}

 

[Gledgard]

<<<Way to post the Microsoft interview question. Hope they don't use google!

We do actually. Google is quite helpful. Not to post for a job, but since it was brought up here, if anyone thinks they have what it takes to answer a question like this (on their own)and is interested in working for Microsoft, feel free to e-mail me at (e-mail address removed).

Gretchen Ledgard
Sr. Talent Scout
Microsoft Corporation

 

[Gledgard]

<<<Way to post the Microsoft interview question. Hope they don't use google!

We do actually. Google is quite helpful. Not to post for a job, but since it was brought up here, if anyone thinks they have what it takes to answer a question like this (on their own)and is interested in working for Microsoft, feel free to e-mail me at (e-mail address removed).

Gretchen Ledgard
Sr. Talent Scout
Microsoft Corporation

 

[Gledgard]

<<<Way to post the Microsoft interview question. Hope they don't use google!

We do actually. Google is quite helpful. Not to post for a job, but since it was brought up here, if anyone thinks they have what it takes to answer a question like this (on their own)and is interested in working for Microsoft, feel free to e-mail me at (e-mail address removed).

Gretchen Ledgard
Sr. Talent Scout
Microsoft Corporation

 

[Gledgard]

<<<Way to post the Microsoft interview question. Hope they don't use google!

We do actually. Google is quite helpful. Not to post for a job, but since it was brought up here, if anyone thinks they have what it takes to answer a question like this (on their own)and is interested in working for Microsoft, feel free to e-mail me at (e-mail address removed).

Gretchen Ledgard
Sr. Talent Scout
Microsoft Corporation

 

[Gledgard]

User error. Didn't mean to spam with 4 posts.

Apologies again,
Gretchen

 

[Alan Connor]

<<<Way to post the Microsoft interview question. Hope they don't use google!

We do actually. Google is quite helpful. Not to post for a job, but since it was brought up here, if anyone thinks they have what it takes to answer a question like this (on their own)and is interested in working for Microsoft, feel free to e-mail me at (e-mail address removed).

Gretchen Ledgard
Sr. Talent Scout
Microsoft Corporation

Sorry. Working for Microsoft is way below cleaning sewers on my list of
preferred jobs.

You couldn't pay me to work with or for that grotesque OS.

I remember fondly the day that I wrote random numbers 25X over the parition
that was home to XPernicious.


Linux/UNIX are where it's at, but SCO can kiss my ass.

How typical of a M$ employee (if you aren't just a fucking troll) to
have a deceptive subject on their post.


AC

 

[Richard Heathfield]

[text re-flowed]

<<<Way to post the Microsoft interview question. Hope they don't use
google!

We do actually. Google is quite helpful. Not to post for a job, but
since it was brought up here, if anyone thinks they have what it takes to
answer a question like this (on their own)and is interested in working for
Microsoft, feel free to e-mail me at <email address elided>

Please adjust your news client's line length setting. There is often some
dispute in Usenet about whether 60, or 65, or 72, or some other comparable
number is the Right Maximum Length for a Usenet line, but I think it's
generally accepted that 278 is way too long.