Printable View
I believe C.A.R. Hoare would be very upset if we had to use just one implementation of his beautiful sorting algorithm. :)
Did you jump to a conclusion there Meldreth? You know what happens when you jump to conclusions like that. :p :p
Echo my left foot. :)
without lots of proof, i trust the library more than i trust an ad hoc implementation by an egotist who thinks he can compete.Quote:
Originally Posted by Adak
i could say you jumped to the conclusion that when i wrote qsort it meant the quicksort algorithm and not c's qsort function. i think what really happened is you intentionally misread my words so you could make a petty jab at me. and you proved it with your next statement. weak.Quote:
Did you jump to a conclusion there Meldreth?
bitter much? :rolleyes:Quote:
Originally Posted by Adak
Hoare's sorting algorithm is named "quick sort", not "qsort".Quote:
Originally Posted by Adak
No no, just having fun. I thought you were, as well.Quote:
Originally Posted by Meldreth
Qsort is quite good, but it's not the very best implementation of Quicksort. The newer C++ version is one such better version.
To be honest, I was thinking of my Quicksort code, but of course, it's not *my* code. It's from a book. I used to tweak it a bit for special sorting jobs. Don't do that anymore, though. There's no need to tweak it, because the faster hardware has made all but the most extremely demanding sorting job, well within what I need.
I'm just a hobby coder, so I'm guessing you're a better programmer than I am. I'm not competing with you, or the standard library version of Quicksort.
As far as I can tell, quicksort is not mandated for the implementation of qsort and std::sort, though typically a variant of quicksort is used.Quote:
Originally Posted by Adak
of course i'm havng fun. you're my new "Special Friend". ;)Quote:
Originally Posted by Adak
so you've checked the source code for every compiler in existence and determined that none of them uses the very best implementation of quicksort? who's measure of "very best" are you using? c++'s? c++ usually uses introsort, and introsort isn't really quicksort. it's a hybrid of quicksort, heapsort, and insertionsort designed to overcome quicksort's flaws. there's nothing stopping a compiler from using introsort for qsort too. or bubblesort. at least c++'s sort has a performance guarantee.Quote:
Originally Posted by Adak
damn skippy. ;) who knows or cares who's better, but my ego dictates that i have to assume it's always me.Quote:
Originally Posted by Adak
I read a book on sorting, and it showed how quicksort could be optimized, if you were careful.
I don't have that ego driven dictate. It would make no sense to think I'm somehow "better", because I clung to some vaporous assumption. I like to be more objective than that.
I recall an episode of the Animaniac's where they were being canceled, and they did this long and very hilarious song about their studio exec. I was in stitches. Never saw a funnier cartoon. Their 50 states and capitals song was quite clever, as well.
Meldreth's "animaniacs" observation fits my theory that quicksort would really be better known as quacksort -- but I said that somewhere else already.
"introsort" must really be the beginning of the end.
I really don't see why any correct sorting algorithm should be known as "quacksort", except maybe bogosort, but even bogosort is correct.Quote:
Originally Posted by MK27
Could give me an example to use as i am strugglling to start off, i know this is asking an annoying question but i have dedicated a lot of time to this and it is getting very frustrating.
thanks
Code:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct element
{
char name[128];
int freq;
};
int cmp_name(const void *a, const void *b);
int cmp_freq(const void *a, const void *b);
void list(struct element *a, int sz);
int main()
{
FILE *fp = fopen("test.txt", "r");
int (*cmp_pf)(const void*, const void*);
struct element elm[200];
int n, opt;
for (n = 0; n < 200; n++)
if (fscanf(fp, "%s%d", elm[n].name, &elm[n].freq) != 2)
break;
fclose(fp);
printf(
"how would you like the data sorted?\n"
"1: by name\n"
"2: by abundance\n> ");
scanf("%d", &opt);
cmp_pf = (opt == 1) ? &cmp_name : &cmp_freq;
qsort(elm, n, sizeof(struct element), cmp_pf);
list(elm, n);
return EXIT_SUCCESS;
}
int cmp_name(const void *a, const void *b)
{
return strcmp(((struct element*)a)->name, ((struct element*)b)->name);
}
int cmp_freq(const void *a, const void *b)
{
return ((struct element*)a)->freq - ((struct element*)b)->freq;
}
void list(struct element *a, int sz)
{
int i;
for (i = 0; i < sz; i++) printf("%s %d\n", a[i].name, a[i].freq);
}
Thank you so much, that has helped me get my head around how to work my program.
I have made a draft of the program using your code as a basis, however i keep getting either an error when runnign from command promt saying " the instruction at 0x7c90100b referenced memory at 0x00000034. the memory could not be read" or if i run through my compiler i get a screen continually displaying pages of 1/4 over again. can;t seem to work out the problem, i'm probably overlooking somthing aren't i?
here is the code:
Code:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct element
{
char name[128];
int abund;
};
int cmp_name(const void *a, const void *b);
int cmp_abund(const void *a, const void *b);
void list(struct element *a, int sz);
int main()
{
char name[128];
FILE *fp;
char s[1000];
{
printf("\nPlease input a file name including extension\n");
gets(name);
fp=fopen(name,"r");
while (s!=NULL)
printf("%s",s);
while (fgets (s,1000,fp)!=NULL);
fclose(fp);
}
fp=fopen(name,"r");
int (*cmp_pf)(const void*, const void*);
struct element elm[1000];
int n, opt;
for (n = 0; n < 1000; n++)
if (fscanf(fp, "%s%d", elm[n].name, &elm[n].abund) != 2)
break;
printf(
"how would you like the data sorted?\n"
"1: by name\n"
"2: by abundance\n> ");
scanf("%d", &opt);
cmp_pf = (opt == 1) ? &cmp_name : &cmp_abund;
qsort(elm, n, sizeof(struct element), cmp_pf);
list(elm, n);
return EXIT_SUCCESS;
}
int cmp_name(const void *a, const void *b)
{
return strcmp(((struct element*)a)->name, ((struct element*)b)->name);
}
int cmp_abund(const void *a, const void *b)
{
return ((struct element*)a)->abund - ((struct element*)b)->abund;
}
void list(struct element *a, int sz)
{
int i;
for (i = 0; i < sz; i++)
printf("%s %d\n", a[i].name, a[i].abund);
}
An error with such a low memory address means you've accessed something relative to a NULL pointer.
"%s%d" does not sound like what you want for your fscanf. Don't you have a seperator such as a comma or space between those fields? I haven't run the program but I'd guess the bug is on that line.
Try printing n after the for loop.
Probably a good idea to read this (Meldreth too):
http://www.akalin.cx/2006/06/23/on-t...ison-function/
nope, same problem occurs