### Thread: using insertion sort with 2d arrays

1. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2003
Posts
15
Rep Power
0

#### help with weird sorting function

Whatever sort this is works for sorting my 2d array by first name. The problem is when I try to sort things by first name. The user in put is in format of first,last. I want this function to sort after the first comma in each row.

Code:
```void sort_names(char names[][LEN], int num, int type)
{

if(type == 1)
{
int i, j;
char temp[LEN];

for(j = 0; j < num; j++)
{
for(i = 0; i < num - 1; i++)
{
if(strcmp(names[i], names[i+1]) > 0)
{
strcpy(temp, names[i]);
strcpy(names[i], names[i+1]);
strcpy(names[i+1], temp);
}
}
}
}```
Last edited by n00b_Programmer; December 13th, 2003 at 03:07 PM.
2. The order of the sorted data is going to be dictated by the result of your comparison function. In that case, you are using strcmp(). One easy solution would be to write your own function, say, firstnamecmp() that takes two name strings, extracts the first names from each, compares them, and returns the same type of thing that strcmp() returns. Then, you could just replace the strcmp() call in that code with a call to firstnamecmp() and it would be sorted properly.

Look up the strchr() function. It finds the first occurence of a character in a string and should help you out a little.

Edit: That's the "bubble sort" algorithm, btw.
Last edited by peenie; December 13th, 2003 at 08:31 PM.
3. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2003
Posts
15
Rep Power
0
Can you please give me an example.
4. OK:
Code:
```#include <stdio.h>
#include <string.h>

#define MAXLEN 30

typedef int (* STRCMPFUNC) (const char *, const char *);

/* this function extracts the nth token from a |-delimited
* string of tokens. the 0th token is the first one. this function
* always returns buf. there's no way to tell if it actually found
* the nth token or not.
*/
char * extract (const char in[MAXLEN], unsigned n, char buf[MAXLEN]) {

int c;
unsigned i = 0;
char temp[MAXLEN];
char *tok;

/* create temporary work buffer, since strtok modifies string. */
strcpy(temp, in);

/* find the nth token */
tok = strtok(temp, "|");
while (i < n) {
if (!(tok = strtok(NULL, "|"))) {
buf[0] = 0; /* empty string */
return buf;
};
++ i;
};

while (*tok && *tok <= 32)
++ tok;

/* copy string to buf */
strcpy(buf, tok);

/* trim trailing whitespace */
for (c = strlen(buf) - 1; c >= 0 && buf[c] <= 32; -- c)
buf[c] = 0;

/* return buf */
return buf;

}

/* this function sorts on the second token in a |-delimited
* string of tokens.
*/
int tok2cmp (const char *s1, const char *s2) {

char buf1[MAXLEN], buf2[MAXLEN];

return strcmp(extract(s1, 1, buf1), extract(s2, 1, buf2));

}

/* this function sorts on the third token in a |-delimited
* string of tokens.
*/
int tok3cmp (const char *s1, const char *s2) {

char buf1[MAXLEN], buf2[MAXLEN];

return strcmp(extract(s1, 2, buf1), extract(s2, 2, buf2));

}

/* generic sorting function, takes as a parameters the number
* of strings to be sorted, the actual strings, and a pointer
* to a comparison function that can compare two strings like
* strcmp does. uses the selection sort algorithm.
*/
void sel_sort (char data[][MAXLEN], unsigned count, STRCMPFUNC compare) {

unsigned i, j, min;
char temp[MAXLEN];

for (j = 0; j < count - 1; ++ j) {
min = j;
for (i = j + 1; i < count; ++ i)
if ((*compare)(data[i], data[min]) < 0)
min = i;
if (min != j) {
strcpy(temp, data[min]);
strcpy(data[min], data[j]);
strcpy(data[j], temp);
};
}

}

/* prints list of strings with a message */
void print_strings (const char data[][MAXLEN], unsigned count, const char *msg) {

unsigned i;

printf("%s:\n", msg);
for (i = 0; i < count; ++ i)
printf("    \"%s\"\n", data[i]);

}

/* main */
int main (void) {

char data[][MAXLEN] = {
"profile | pm | buddy",
"forum | devshed | search",
"apple | zebra | joik",
"z | b | c",
"edit | quote | logged",
"php | sql | c++",
"x | y | a"
};
unsigned size = sizeof(data) / MAXLEN;

print_strings(data, size, "unsorted");

sel_sort(data, size, &strcmp);
print_strings(data, size, "sorted with strcmp");

sel_sort(data, size, &tok2cmp);
print_strings(data, size, "sorted with tok2cmp");

sel_sort(data, size, &tok3cmp);
print_strings(data, size, "sorted with tok3cmp");

return 0;

}```
The only new concept to you there should be function pointers. The sel_sort function performs a selection sort using the specified function as the sort function (in place of where you'd normally put strcmp). As you see, I can use strcmp itself, or any other sort function that I write. That function will determine how the data is sorted. Consider this: The only information the sort algorithm itself has about how the elements should be ordered comes from the comparison function. So, it's all in how you compare things.

The extract function simply loops with strtok() to get the nth token of a | delimited string of tokens. The tok2cmp and tok3cmp functions are two "custom" comparison functions that only compare the 2nd or 3rd token of such strings.

If you know that you are only going to be dealing with 2 tokens separated by a ',' then you can use strchr() as an alternative to strtok() to find the ,. It's up to you, the technique would be a bit dfferent with strchr().

The program should output the following:
Code:
```unsorted:
"profile | pm | buddy"
"forum | devshed | search"
"apple | zebra | joik"
"z | b | c"
"edit | quote | logged"
"php | sql | c++"
"x | y | a"
sorted with strcmp:
"apple | zebra | joik"
"edit | quote | logged"
"forum | devshed | search"
"php | sql | c++"
"profile | pm | buddy"
"x | y | a"
"z | b | c"
sorted with tok2cmp:
"z | b | c"
"forum | devshed | search"
"profile | pm | buddy"
"edit | quote | logged"
"php | sql | c++"
"x | y | a"
"apple | zebra | joik"
sorted with tok3cmp:
"x | y | a"
"profile | pm | buddy"
"z | b | c"
"php | sql | c++"
"apple | zebra | joik"
"edit | quote | logged"
"forum | devshed | search"```
Note how the strings are sorted.

J.C.

Edit: The notation for function pointers that I used, IMHO, makes things clearer. However, you don't have to use & to take the address of a function, or * to dereference a function pointer; at least in most of the compilers I've used. So the following two things would be the same:
Code:
```// this:
STRCMPFUNC func;
func = &strcmp;
(*func)("function", "pointer");

// and this:
STRCMPFUNC func;
func = strcmp;
func("function", "pointer");```
It's just a matter of preference, I guess.
Last edited by peenie; December 14th, 2003 at 08:28 PM.
5. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2003
Posts
15
Rep Power
0
Thank you very much.