尝试qsort实现 [英] attempt at qsort implementation
问题描述
我有空闲时间并决定尝试实施标准库
qsort。这是一个非常简单的尝试，但它似乎工作。我必须指出效率对我来说根本不是问题，而且这可以说是纯粹的玩具。我很清楚这不是实现快速排序算法的最快方式，但我基本上只是想尝试使用
制作一个泛型函数。 。我测试了几个结构阵列
包含各种类型（这个，当然，并不意味着它是'b
正确，即使是远射:)。我将不胜感激任何建设性的
评论。下面的代码是一个片段。包含所有必需的头文件，并且uchar是unsigned char的typedef。
谢谢。
void do_swap_（void * a，void * b，size_t sz）
{
uchar t;
uchar * i = a;
uchar * j = b;
while（sz）{
t = * i;
* i ++ = * j ;
* j ++ = t;
--sz;
}
}
void quick_sort（void * v，size_t count，size_t sz，int（* cmp）（const void *，
const void *））
{
uchar * t = v;
uchar * x，* y;
uchar * r;
if（count）{
x = y = t;
r = t +（count-1）* sz;
for（; y< r ; y + = sz）
if（cmp（y，r）< 0）{
do_swap_（x，y，sz）;
x + = sz;
}
do_swap_（x，r，sz）;
quick_sort（t，（xt）/ sz， sz，cmp）;
quick_sort（x + sz，count-（xt）/ sz - 1，sz，cmp）;
}
}
I had some spare time and decided to try to implement the standard library
qsort. This is a pretty simpleminded attempt, but it seems to be working. I
have to point out that efficiency is not at all an issue for me, and this is
purely a toy, so to speak. I''m quite aware that this is not the quickest way
to implement the quicksort algorithm, but I basically just wanted to try to
make a "generic function". I tested it with a few arrays of structures
containing all sorts of types (this, ofcourse, doesn''t mean that it''s
correct, even by a long shot :). I would appreciate any and all constructive
comments. The code below is a snippet. All the necessary headers are
included and uchar is a typedef for unsigned char.
Thank you.
void do_swap_(void *a, void *b, size_t sz)
{
uchar t;
uchar *i = a;
uchar *j = b;
while (sz) {
t = *i;
*i++ = *j;
*j++ = t;
--sz;
}
}
void quick_sort(void *v, size_t count, size_t sz, int (*cmp)(const void *,
const void *))
{
uchar *t = v;
uchar *x, *y;
uchar *r;
if (count) {
x = y = t;
r = t+(count-1)*sz;
for(; y<r; y += sz)
if (cmp(y, r)<0) {
do_swap_(x, y, sz);
x += sz;
}
do_swap_(x, r, sz);
quick_sort(t, (x-t)/sz, sz, cmp);
quick_sort(x+sz, count-(x-t)/sz - 1, sz, cmp);
}
}
推荐答案
buda写道：
我有一些空余时间，并决定尝试实施标准库
qsort。这是一个非常简单的尝试，但它似乎工作。我必须指出效率对我来说根本不是问题，而且这纯粹是一个玩具，可以这么说。我很清楚这不是实现快速排序算法的最快方式，但我基本上只是想尝试制作一个通用函数。我用一些包含各种类型的结构阵列进行了测试（这个，当然，并不意味着它是正确的，即使是长镜头也是如此）。
我将感谢任何和所有建设性的评论。下面的代码是一个片段。包含所有必需的标题，uchar是unsigned char的typedef。
谢谢。
这个实现可能会在已经订购的大型数组上耗尽内存
。
如果数组在排序，
然后（xt）/ sz将等于count - 1
并且你最终将计算-1 - 递归水平。 />
如果count很大，该函数可能会使程序崩溃。
void do_swap_（void * a，void * b，size_t sz）
{
uchar t;
uchar * i = a;
uchar * j = b;
while（sz）{
t = * i;
* i ++ = * j;
* j ++ = t;
--sz;
}
}
void quick_sort（void * v，size_t count，
size_t sz，int（* cmp）（const void *，
const void *））
{
uchar * t = v;
uchar * x，* y;
uchar * r;
if（count）{
x = y = t;
r = t +（count-1）* sz;
for（; y< r; y + = sz）
if（cmp（y，r）< 0）{
do_swap_（x，y，sz）;
x + = sz;
}
do_swap_（x，r，sz）;
quick_sort（t，（xt）/ sz，sz，cmp）;
quick_sort（x + sz，count-（xt）/ sz - 1，sz，cmp）;
}
}
I had some spare time and decided to try to implement the standard library
qsort. This is a pretty simpleminded attempt, but it seems to be working. I
have to point out that efficiency is not at all an issue for me, and this is
purely a toy, so to speak. I''m quite aware that this is not the quickest way
to implement the quicksort algorithm, but I basically just wanted to try to
make a "generic function". I tested it with a few arrays of structures
containing all sorts of types (this, ofcourse, doesn''t mean that it''s
correct, even by a long shot :).
I would appreciate any and all constructive
comments. The code below is a snippet. All the necessary headers are
included and uchar is a typedef for unsigned char.
Thank you.
This implementation will probably run out of memory
on large already ordered arrays.
If the array is in order prior to sorting,
then (x-t)/sz will be equal to count - 1
and you''ll wind up with about count - 1, levels of recursion.
If count is large, the function could crash the program.
void do_swap_(void *a, void *b, size_t sz)
{
uchar t;
uchar *i = a;
uchar *j = b;
while (sz) {
t = *i;
*i++ = *j;
*j++ = t;
--sz;
}
}
void quick_sort(void *v, size_t count,
size_t sz, int (*cmp)(const void *,
const void *))
{
uchar *t = v;
uchar *x, *y;
uchar *r;
if (count) {
x = y = t;
r = t+(count-1)*sz;
for(; y<r; y += sz)
if (cmp(y, r)<0) {
do_swap_(x, y, sz);
x += sz;
}
do_swap_(x, r, sz);
quick_sort(t, (x-t)/sz, sz, cmp);
quick_sort(x+sz, count-(x-t)/sz - 1, sz, cmp);
}
}
-
pete
--
pete
>我有一些空余时间并决定尝试实现标准库
>I had some spare time and decided to try to implement the standard library
qsort。这是一个非常简单的尝试，但它似乎工作。我必须指出效率对我来说根本不是问题，而且这纯粹是一个玩具，可以这么说。我很清楚这不是实现快速排序算法的最快方式，但我基本上只是想尝试制作一个通用函数。
qsort（）不需要实现任何特定的排序算法。
它只是应该排序。它没有指定如何。冒泡分类
不是无效的实现。递归bogosort [*]（
的运行时间相当于O（e ** infinity））可能是一个无效的
实现，因为它永远不会完成。
我用一些结构阵列测试了它们包含各种类型（这个，当然，并不意味着它是正确的，即使是长镜头： ）。我将不胜感激任何建设性的评论。下面的代码是一个片段。包含所有必需的标题，uchar是unsigned char的typedef。
谢谢。
qsort. This is a pretty simpleminded attempt, but it seems to be working. I
have to point out that efficiency is not at all an issue for me, and this is
purely a toy, so to speak. I''m quite aware that this is not the quickest way
to implement the quicksort algorithm, but I basically just wanted to try to
make a "generic function".
qsort() is not required to implement any particular sort algorithm.
It''s just supposed to sort. It''s not specified HOW. A bubble sort
is not an invalid implementation. A recursive bogosort[*] (which
operates in time equivalent to O(e**infinity)) is probably an invalid
implementation since it NEVER finishes.
I tested it with a few arrays of structures
containing all sorts of types (this, ofcourse, doesn''t mean that it''s
correct, even by a long shot :). I would appreciate any and all constructive
comments. The code below is a snippet. All the necessary headers are
included and uchar is a typedef for unsigned char.
Thank you.
如果count == 1，算法无论如何做比较。我知道你
在这里不是真正的效率，但这似乎有点
奇怪。
如果sz == 0，各种奇怪和令人讨厌的事情都会发生，但是打电话的人要求它。
似乎这个算法可能最终会递归很多。
这可能是大量数据的问题。
这里值得一试的是你的算法运作得多好
带有伪造比较例程（例如，一个总是返回-1，或者
，其中cmp（a，b）不能保证等于-cmp（b，a））。一些
的实现最终会在这种
的情况下超出传入的数组。
[*]技术说明：bogosort通过创建来运行所有可能的
排序数组的订单，确定订单中有多少元素
，并返回元素数量最少的订单
按顺序排序并返回第一个。在其他
的单词中，它将N个元素的排序问题转化为排序之一
N！元素。
递归bogosort使用bogosort按可能的顺序排序
元素数量不按顺序，从而解决了问题
将N个元素排序为排序N !!!!!!!!!!!!!!!!!!!!!!!!!! ....
元素。 Bogosorts通常包括其他性能浪费
代码，例如：
while（malloc（INT_MAX））fork（）;
因为它们永远不会无论如何都要完成。
Gordon L. Burditt
If count == 1, the algorithm does a compare anyway. I know you
weren''t going for real efficiency here, but this seems a bit
strange.
If sz == 0, various wierd and obnoxious things will happen, but
the caller IS asking for it.
It seems like this algorithm could end up recursing a lot.
This could be a problem with large amounts of data.
One thing worth checking here is how well your algorithm will operate
with a bogus compare routine (e.g. one which always returns -1, or
one for which cmp(a,b) is not guaranteed to equal -cmp(b,a) ). Some
implementations end up going outside the passed-in array in such
circumstances.
[*] Technical note: a bogosort operates by creating all possible
orders of the sorted array, determining how many elements are out
of order, and returns the order with the least number of elements
out of order by sorting them and returning the first one. In other
words, it turns the problem of sorting N elements into one of sorting
N! elements.
A recursive bogosort uses bogosort to sort the possible orders by
number of elements out of order, thereby turning the problem of
sorting N elements into one of sorting N!!!!!!!!!!!!!!!!!!!!!!!!!!....
elements. Bogosorts typically include other performance-wasting
code such as:
while (malloc(INT_MAX)) fork();
since they will never finish anyway.
Gordon L. Burditt
Gordon Burditt写道：
Gordon Burditt wrote:
我有一些空余时间，并决定尝试实现标准库qsort。
I had some spare time and decided to try to
implement the standard library qsort.
qsort（）不需要实现任何特定的排序算法。<它只是应该排序。
这里值得检查的一件事是你的算法在伪造比较程序中的运行情况如何（例如总是返回-1的那个，或者是一个cmp（a，b）不是保证等于-cmp（b，a））。
在这种情况下，某些实现最终会超出传入的
数组。
qsort() is not required to implement any particular sort algorithm.
It''s just supposed to sort.
One thing worth checking here is how well your algorithm will operate
with a bogus compare routine (e.g. one which always returns -1, or
one for which cmp(a,b) is not guaranteed to equal -cmp(b,a) ).
Some implementations end up going outside the passed-in
array in such circumstances.
具有伪造比较例程的qsort的行为未定义，
那么重点是什么？
-
pete
The behavior of qsort with a bogus compare routine, is undefined,
so what''s the point?
--
pete
这篇关于尝试qsort实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
