P
pateldm15
How do I sort an string array using pointers
I
Ian Collins
How do you think? Post an attempt and you will get help.
E
erfan
C
CBFalconer
Friedrich said:
Simpler: Make a singly linked list and apply merge sort.
F
Friedrich Dominicus
Tip: qsort + strcmp
Have a nice day of C programming
Friedrich
S
santosh
CBFalconer said:
How is this method simpler?
A
aarklon
what about this attempt
void sort(char *m[10])
{
int a,b,x;
char *temp;
for(a=0;a < 10;a++)
for(b = a + 1;b<10;b++)
{
x=0;
while(*(*(m+a) +x))
{
if( *(*(m+a)+x) > *(*(m + b)+x) )
{
temp = *(m+a);
*(m+a) = *(m +b);
*(m + b) = temp;
break;
}
else if( *(*(m+a)+x) < *(*(m+b)+x) )
break;
else
x++;
}
}
}
S
santosh
P
pete
/* BEGIN pt_sort.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SORT_FUNCTIONS { \
no_sort, "Original order of the test arrays:", \
i_sort, "Stable insertionsort:", \
slsort, "Nonstable simple selection sort;\nfour is " \
"after nine, and three is after eight:", \
qsort, "Standard library qsort;\n" \
"unspecified ordering of equal keys:" \
}
#define NUMBERS { \
"one", "two","three","four","five", \
"six","seven","eight","nine", "ten" \
}
#define NMEMB (sizeof numbers / sizeof *numbers)
#define SORTS (sizeof s_F / sizeof *s_F)
int lencomp(const void *a, const void *b);
void no_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void slsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
int main(void)
{
size_t element, sort;
struct sf {
void (*function)(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
const char *description;
} s_F[] = SORT_FUNCTIONS;
const char *numbers[] = NUMBERS;
char *copy[NMEMB];
puts("\n/* BEGIN output from pt_sort.c */\n\n"
"Arrays of type char *,\n"
"are being sorted by string length.\n");
for (sort = 0; sort != SORTS; ++sort) {
puts(s_F[sort].description);
memcpy(copy, numbers, sizeof copy);
s_F[sort].function(copy, NMEMB, sizeof *copy, lencomp);
for (element = 0; element != NMEMB; ++element) {
puts(copy[element]);
}
putchar('\n');
}
puts("/* END output from pt_sort.c */");
return 0;
}
int lencomp(const void *a, const void *b)
{
const size_t a_len = strlen(*(const char **)a);
const size_t b_len = strlen(*(const char **)b);
return b_len > a_len ? -1 : b_len != a_len;
}
void no_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
base, nmemb, size, compar;
}
void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low, *p1, *p2, *end, swap;
if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}
void slsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t tail;
unsigned char *array, *first, *middle, *p1, *p2, *end, swap;
for (array = base; nmemb-- > 1; array += size) {
middle = first = array + size;
tail = nmemb;
while (--tail != 0) {
middle += size;
if (compar(first, middle) > 0) {
first = middle;
}
}
if (compar(array, first) > 0) {
p1 = array;
p2 = first;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
}
}
}
/* END pt_sort.c */
V
vippstar
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int
cmpstringp(const void *p1, const void *p2)
{
/* The actual arguments to this function are "pointers to
pointers to char", but strcmp() arguments are "pointers
to char", hence the following cast plus dereference */
return strcmp(* (char * const *) p1, * (char * const *) p2);
}
int
main(int argc, char *argv[])
{
int j;
if(argc > 1) {
qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);
for (j = 1; j < argc; j++)
puts(argv[j]);
}
exit(EXIT_SUCCESS);
}
P
pete
The type of your strcmp arguments is (char *const).
The strcmp parameter type is (const char *).
This way would be more better:
return strcmp(* (const char **) p1, * (const char **) p2);
H
Harald van Dijk
char * can be implicitly converted to const char *.
argv is declared as char *[]. argv[n] (which is what p1 and p2 point to)
is a char *. You shouldn't access a char * as if it were a const char *.
I'm not saying it's not allowed, because I'm not sure about that, but I
consider it poor style at least.
P
pete
=?UTF-8?q?Harald_van_D=C4=B3k?= said:
However,
strcmp *will* access its arguments as type (const char *).
A function call to strcmp,
implies that there are parameters of type (const char *)
being initialized with the values of the arguments.
The values of those arguments should be type (const char *).
int strcmp(const char *s1, const char *s2);
H
Harald van Dijk
No, it won't. It will access its parameters as type (const char *), and
its parameters *are* type const char *, as the result of the implicit
conversion from the arguments (of type char *) to const char *. You can
compare it to this:
Good:
char a = 'x';
int b = a;
const int *c = &b;
Bad:
char a = 'x';
const int *c = (int *) &a;
C
CBFalconer
santosh said:
Merge sort code is simple. Input is simple, because you just
extend a linked list by one for each input line. No problem as
long as memory holds out.
Here is suitable stuff for the merge sort.
/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */
#ifndef listops_h_
#define listops_h_
#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */
/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;
/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);
/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);
/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */
/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */
#endif
/* end listops.h */
/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */
/* using stdops.h, 16 Sept. 2001 */
#include "stdops.h" /* bool, true, false, not, and, or, xor */
#include "listops.h"
/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;
if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */
/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;
p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);
/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */
/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;
p = &n;
n.next = p;
while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;
/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */
/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;
if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */
return root;
} /* mergesort */
/* end listops.c */
Combine that with ggets and puts and about 10 lines of code and you
are done. Basically:
root = NULL; /* empty list */
while (0 = ggets(&line))
if (newnode = malloc(sizeof *newnode)) {
newnode->data = line;
newnode->next = root;
root = newnode;
}
root = mergesort(root, cmp);
while (root) {
puts(root->data); /* display results */
tmp = root->next;
free(root);
root = tmp;
}
You have to put together the cmp function, which picks the strings
out of the nodes and passes them to strcmp. In my world everybody
has the equivalent of listops and ggets handy.
T
Tor Rustad
Yes, assuming argv[0] represent the program name, I have yet to see an
environment where this isn't the case. Anybody knows of one?
S
santosh
Tor said:
Not specifically but I would guess that in environments where the C
program is the only program on the device, it would be meaningless for
it to have a name.
M
Martien Verbruggen
[ snip of about 150 lines of code ]
But qsort is a standard function, that you do not have to implement.
Therefore it is simpler to just use that, rather than to implement any
sort algorithm yourself. Using qsort() and strcmp, as suggested before,
is likely to take less than 15 lines of code.
Also, the input is an array, not a linked list, and a good assumption
would be that the array should be sorted in place, or at least that the
output should be a sorted array. Translating it into a linked list,
sort, and then translating back, is by no means simpler than just using
a method that acts directly on the data structure at hand.
Besides that, you do not know how qsort is implemented internally. It's
a bit hard to make judgements on the complexity of the algorithm without
that knowledge.
Martien
C
cr88192
santosh said:
when your program consists of source files which are dynamically loaded and
compiled, there is no meaningful name to pass to main...
P
pete
=?UTF-8?q?Harald_van_D=C4=B3k?= said:
I can't parse out which effect you say occurs:
"... as the result of the implicit conversion from the arguments
(of type char *) to const char *."
At least in the bad example, your code acknowledges
that the purpose of the cast is to convert the value
to the type of the object receiving the value.
The whole point of casting a pointer initializer,
is to convert the value
to the type of the object receiving the value.
Recording the type history of the value,
is not the purpose of the cast.