如何改善这种？ [英] How to improve this sort?
问题描述
大家好，
我为浮动写了一个升序排序程序。这似乎可以做到这一点，但对于超过10,000的元素，它变得非常缓慢。很多
与之前排序的元素进行了无用的比较。我想要使用一个保持索引的函数，以选择性地迭代
而不是未排序的元素。但是我无法想办法。
有什么想法可以改善日常工作并获得更好的成绩吗？
感谢所有人。
#include< errno.h>
#include< stdio.h>
#include< stdlib.h> ;
#include< time.h>
#define MAX_ALLOC 1000000UL
void sortf_asc（float * a，unsigned long elem）{
int sort_occured = 0;
unsigned long start_offset = 0，current_pos，c1;
float tmp;
while（start_offset< elem - 2）{
for（c1 = 1 +（current_pos = start_offset）; c1< elem; c1 ++）{
if（a [current_pos] a [c1]）{
tmp = a [c1];
a [c1] = a [current_pos];
a [current_pos] = tmp;
current_pos = c1;
sort_occured = 1;
}
}
if（sort_occured）sort_occured = 0;
else start_offset ++;
}
return; < br $> b $ b}
int main（int argc，char ** argv）{
char * usage ="用法：\ n \ nnPROGRAM ELEMENTS \ nn'nnments - 数量
要排序的元素，（最大值=％lu）\ n"，
* fopenfail ="无法打开文件。\ n"，
* tail = NULL;
unsigned long elements = 0，c1;
float * farray = NULL;
FILE * outfp = NULL;
if（argc< 2）{fprintf（stderr，usage，MAX_ALLOC）;返回EXIT_FAILURE; }
else {
errno = 0;
elements = strtoul（argv [1]，& tail，0）;
if（errno == EINVAL || errno == ERANGE）{
fprintf（stderr，用法，MAX_ALLOC）;
返回EXIT_FAILURE;
}
else if（elements< 2 || elements MAX_ALLOC）{
fprintf（stderr，usage，MAX_ALLOC）;
返回EXIT_FAILURE;
}
}
farray = malloc（elements * sizeof * farray）;
if（！farray）{
fprintf（stderr，Memory allocation failed.\ n）;
返回EXIT_FAILURE;
}
else {
srand（（unsigned int）time（NULL））;
for（c1 = 0; c1< ; elements; c1 ++）farray [c1] =（float）rand（）;
}
outfp = fopen（" unsorted"，" w" ;）;
if（！outfp）{
fprintf（stderr，fopenfail）;
free（farray）;
返回EXIT_FAILURE;
}
else {
for（c1 = 0; c1<要素; c1 ++）
fprintf（outfp，" [％lu]：％f \ n"，c1，farray [c1]）;
fclose（outfp）;
outfp = NULL;
}
sortf_asc（farray，elements）;
outfp = fopen（" sorted"，" w"）;
if（！outfp）{
fprintf（stderr，fopenfail）;
free（farray）;
返回EXIT_FAILURE;
}
else {
for（c1 = 0; c1< elements; c1 ++）
fprintf（outfp，" [％lu]：％f \ n"，c1，farray [c1]）;
fclose（outfp）;
}
返回0;
}
-
电子邮件：句柄，（点分隔），在gmail dot com。
Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
Thanks to all.
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ALLOC 1000000UL
void sortf_asc(float *a, unsigned long elem) {
int sort_occured = 0;
unsigned long start_offset = 0, current_pos, c1;
float tmp;
while(start_offset < elem - 2) {
for(c1 = 1 + (current_pos = start_offset); c1 < elem; c1++) {
if(a[current_pos] a[c1]) {
tmp = a[c1];
a[c1] = a[current_pos];
a[current_pos] = tmp;
current_pos = c1;
sort_occured = 1;
}
}
if(sort_occured) sort_occured = 0;
else start_offset++;
}
return;
}
int main(int argc, char **argv) {
char *usage = "Usage:\n\nPROGRAM ELEMENTS\n\nELEMENTS - Number of "
"elements to sort, (max. = %lu)\n",
*fopenfail = "Failed to open file.\n",
*tail = NULL;
unsigned long elements = 0, c1;
float *farray = NULL;
FILE *outfp = NULL;
if(argc < 2){ fprintf(stderr, usage, MAX_ALLOC); return EXIT_FAILURE; }
else {
errno = 0;
elements = strtoul(argv[1], &tail, 0);
if(errno == EINVAL || errno == ERANGE) {
fprintf(stderr, usage, MAX_ALLOC);
return EXIT_FAILURE;
}
else if(elements < 2 || elements MAX_ALLOC) {
fprintf(stderr, usage, MAX_ALLOC);
return EXIT_FAILURE;
}
}
farray = malloc(elements * sizeof *farray);
if(!farray) {
fprintf(stderr, "Memory allocation failed.\n");
return EXIT_FAILURE;
}
else {
srand((unsigned int)time(NULL));
for(c1 = 0; c1 < elements; c1++) farray[c1] = (float)rand();
}
outfp = fopen("unsorted", "w");
if(!outfp) {
fprintf(stderr, fopenfail);
free(farray);
return EXIT_FAILURE;
}
else {
for(c1 = 0; c1 < elements; c1++)
fprintf(outfp, "[%lu]: %f\n", c1, farray[c1]);
fclose(outfp);
outfp = NULL;
}
sortf_asc(farray, elements);
outfp = fopen("sorted", "w");
if(!outfp) {
fprintf(stderr, fopenfail);
free(farray);
return EXIT_FAILURE;
}
else {
for(c1 = 0; c1 < elements; c1++)
fprintf(outfp, "[%lu]: %f\n", c1, farray[c1]);
fclose(outfp);
}
return 0;
}
--
Email: The handle, (dot seperated), at gmail dot com.
推荐答案
At_sea_with_C说：
At_sea_with_C said:
Hello all，
我为浮点数写了一个升序排序程序。这似乎可以做到这一点，但对于超过10,000的元素，它变得非常缓慢。很多
与之前排序的元素进行了无用的比较。我想要使用一个保持索引的函数，以选择性地迭代
而不是未排序的元素。但我无法想办法。
有什么想法可以改善日常工作并获得更好的成绩吗？
Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
你似乎在使用Bubble Sort，这是最慢的排序之一。
如果你不被允许打电话给qsort，我建议看看由Kernighan和Ritchie撰写的第二版
第62页的C编程语言，其中
实现了DL Shell的排序算法。将int v []更改为float v [] -
应该是唯一必要的更改。
-
Richard Heathfield
Usenet是一个奇怪的地方 - dmr 29/7/1999
http://www.cpax.org.uk
电子邮件：rjh在上述域名中， - www。
You seem to be using Bubble Sort, which is one of the slowest sorts around.
If you are not allowed to call qsort, I suggest taking a look at page 62 of
"The C Programming Language", 2nd edition, by Kernighan and Ritchie, which
implements D L Shell''s sorting algorithm. Change int v[] to float v[] -
that should be the only necessary change.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Richard Heathfield写道：
Richard Heathfield wrote:
At_sea_with_C说：
At_sea_with_C said:
> Hello all，
我为浮点数编写了一个升序排序程序。这似乎做了这项工作，但对于超过10,000的元素，它变得非常缓慢。与先前排序的元素进行了许多无用的比较。我想要使用一个保持索引的函数来选择性地迭代未排序的元素。但是我无法想办法。
任何改善日常工作并获得更好成绩的想法？
>Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
您似乎正在使用冒泡排序，这是最慢的排序之一。
如果您不被允许拨打qsort，我建议看看由Kernighan和Ritchie撰写的第二版
第62页的C编程语言，其中
实现了DL Shell的排序算法。将int v []更改为float v [] -
应该是唯一必要的更改。
You seem to be using Bubble Sort, which is one of the slowest sorts around.
If you are not allowed to call qsort, I suggest taking a look at page 62 of
"The C Programming Language", 2nd edition, by Kernighan and Ritchie, which
implements D L Shell''s sorting algorithm. Change int v[] to float v[] -
that should be the only necessary change.
我在纸上制定了逻辑。我们被告知要排序一组N
整数或浮点数。我选择花车没有特别的原因。它只是
一个入门课程，我们还没有涵盖排序，这就是为什么
我不得不考虑一下这个。我会在你的图书馆看看你提到的这本书是否可以提供。
只需一个问题。排序整数与排序浮动不同吗？用
换句话说，我可以在我的代码中将int替换为浮点数
并让它工作正常吗？我不能想为什么不这样做，但我刚开始做C，
所以你的建议会有所帮助。
感谢您的回复。 />
-
电子邮件：手柄，（点分开），在gmail dot com。
I worked out the logic on paper. We were just told to sort an array of N
integers or floats. I chose floats for no particular reason. It''s just
an introductory class, and we haven''t covered sorting yet, which is why
I had to think for a while for this one. I will see if the book you
mention is available in our library.
Just one question. Is sorting integers different from sorting floats? In
other words, can I just substitute int for float everywhere in my code
and have it work okay? I can''t think why not, but I am just starting C,
so your advice would be helpful.
Thanks for the reply.
--
Email: The handle, (dot seperated), at gmail dot com.
At_sea_with_C说：
At_sea_with_C said:
Richard Heathfield写道：
Richard Heathfield wrote:
> At_sea_with_C说：
>At_sea_with_C said:
>>大家好，
我为浮点数编写了一个升序排序程序。这似乎做了这项工作，但对于超过10,000的元素，它变得非常缓慢。与先前排序的元素进行了许多无用的比较。我想要使用一个保持索引的函数来选择性地迭代未排序的元素。但是我无法想办法。
任何改善日常工作并获得更好成绩的想法？
>>Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
您似乎正在使用冒泡排序，这是最慢的排序之一。如果你不被允许打电话给qsort，我建议你看一下Kernighan的第二版The C Programming Language第62页
Ritchie，它实现了DL Shell的排序算法。将int v []
更改为float v [] - 这应该是唯一必要的更改。
You seem to be using Bubble Sort, which is one of the slowest sorts
around. If you are not allowed to call qsort, I suggest taking a look at
page 62 of "The C Programming Language", 2nd edition, by Kernighan and
Ritchie, which implements D L Shell''s sorting algorithm. Change int v[]
to float v[] - that should be the only necessary change.
我在纸上制定了逻辑。
I worked out the logic on paper.
....和（重新）发明冒泡排序。我们很多人这样做。 :-)但是，当你发现
时，它变得非常慢得令人震惊。
....and (re)invented Bubble Sort. Lots of us do that. :-) But, as you
discovered, it gets appallingly slow appallingly fast.
我们刚刚被告知排序一个N数组整数或浮点数。我选择
花车没有特别的原因。它只是
一个入门课程，我们还没有涵盖排序，这就是为什么
我不得不考虑一下这个。我会在我们的图书馆看看你提到的这本书是否可以提供。
We were just told to sort an array of N integers or floats. I chose
floats for no particular reason. It''s just
an introductory class, and we haven''t covered sorting yet, which is why
I had to think for a while for this one. I will see if the book you
mention is available in our library.
这是一个很好的计划。或者参见：例如：
http：// www。 nist.gov/dads/HTML/shellsort.html
只有一个问题。排序整数与排序浮动不同吗？用
换句话说，我可以在我的代码中将int替换为浮点数
并让它工作正常吗？我不能想为什么不这样做，但我刚开始做C，
所以你的建议会有所帮助。
Just one question. Is sorting integers different from sorting floats? In
other words, can I just substitute int for float everywhere in my code
and have it work okay? I can''t think why not, but I am just starting C,
so your advice would be helpful.
是的，你可以这样做。
-
Richard Heathfield
Usenet是一个奇怪的地方 - dmr 29/7/1999
http://www.cpax.org.uk
电子邮件：rjh在上述域名中， - www。
Yes, you can do that.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
这篇关于如何改善这种？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
