u****g
发帖数: 402 | 1 online测试题，哪个function 可以来 sort array of string，
qsort or sort？
网上搜出来的都是在讲怎么用qsort来排序array of string, 但sort应该更好用并且更
简单吧。 |
|
a***n
发帖数: 1616 | 2 优化部分基本是抄的glibc qsort的，不过glibc的写得太烂了，只要了它的idea ...
1. median-3 pivot
2. 3-way partition with optimized tight inner loops
3. non-recursive, w/ log(n) stack, always finish shorter partition first
4. qsort + final insertion sort hybrid with THRESH=5
5. optimized tight inner loop for final insertion sort |
|
b*********n
发帖数: 1258 | 3 想要用qsort来sort一个char array, code如下，但是seg fault
不知道为什么，大家指点一下
#include
#include
#include
char* inString = "ncdoscndisoc";
int compare (const void* a, const void* b)
{
return ((*(char*)a) - (*(char*)b) );
}
int main ()
{
qsort (inString, 12, sizeof(char), compare);
for (int n=0; n<12; n++)
printf ("%c ",inString[n]);
return 0;
} |
|
e******d
发帖数: 310 | 4 I want to sort strings using qsort(), and try the following code, but doesn
't work. Could you please help me out. Thank you.
=============================================
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int mystrcmp(const void * str1, const void * str2)
{
return strcmp( (const char*)str1, (const char*)str2 ) ;
}
int main()
{
int n = 4;
char *pstr[] = {"God", "Bed", "Act", "Cup"};
qsort(pstr, n, sizeof(char*), mystrcmp);
int i = 0;
for(i = 0; |
|
X****r
发帖数: 3557 | 5 qsort passes pointers to the objects being compared. Your objects
in the array are "char *", thus the comparison function parameters
have actual type "char **".
For example, if you're sorting integers, you would do:
int myintcmp(const void *p1, const void *p2) {
return *(const int*)p1 - *(const int *)p2;
}
int data[] = {1,3,2,4};
qsort(data, sizeof(data)/sizeof(data[0]), sizeof(data[0]), myintcmp);
Just replace "int" in above example with "char *" you'll see.
const*)str2); |
|
c*******n
发帖数: 63 | 6 只知道STL Algorithm里有sort，不知道有qsort
ps: sort适合有RandomAccessIterator的container |
|
p***o
发帖数: 1252 | 7 It really doesn't matter which language you are using.
Actually qsort is a good example to show someone familiar with C
the idea of functor in C++. While C++ automatically matches
(or finds a mismatch of) the types for std::sort, in C you have
to do it by hand and be very careful; otherwise you will get
the same error as LZ. |
|
l*********s
发帖数: 5409 | 8 [question] what is the time complexity of qsort in standard c libarary(GCC,
more specifically)? Is is based on quick sort algorithm? |
|
|
d****n
发帖数: 1637 | 9 That would be only the partial answer.
if the sequence/array to be sorted has very good randomness(pivot good),
then the O(Nlog(N)).
if the array has been almost sorted or bad chose of pivot, the run time
would be O(N^2).
The Glib C qsort is a text-book implementation, which is terrible slow on
sorting on huge data set.
See introsort. or C++ stl::sort if you are looking for a industry solution. |
|
l*********s
发帖数: 5409 | 10 Thank you! How about qsort in GCC? |
|
y*********e
发帖数: 518 | 11 O(nlogn):
qsort 和 mergesort 都可以达到O(nlogn)，但是 qsort 的常数因子比 mergesort 低
很多。所以，一般情况下 qsort 会更快。
O(n^2):
虽然 qsort 的最坏情况是 O(n^2)，但是要达到这个最坏情况不容易。对于实现的较好
randomized qsort，达到这个最坏情况的几率接近于 1 / n^logn。这个数值是非常低
的。
stable vs unstable:
通常 qsort 的实现是 unstable的，mergesort 的实现是 stable 的。
还有一点，qsort 一般是 inplace 的，mergesort 一般的实现不是 inplace 的。
random access:
qsort 要求可以对排序对象进行 random access。对于排序主内存中的 array 就很实
用。但是，遇到排序的对象不支持 random access，那么 qosrt 就不行了。比如排序
linked list，或者做磁盘文件排序。。利用这一点，可以很容易的用 mergesort 实现
并发排序。 |
|
N**********e
发帖数: 32 | 12 Is the Erlang qsort implementation the most concise one?
qsort([]) -> [];
qsort([Pivot|T]) ->
qsort([X || X <- T, X =< Pivot])
++ [Pivot] ++
qsort([X || X <- T, X > Pivot]). |
|
a*****e
发帖数: 1700 | 13 qsort [] = []
qsort (x:xs) = qsort m ++ [x] ++ qsort n
where m = [ a | a <- xs, a < x ]
n = [ b | b <- xs, b >= x]
一分钟不到。 |
|
y*********e
发帖数: 518 | 14 感觉对方是在问 Closure。
这个是 Java 对 Lambda 表达式的实现。Java 7 已经确定在语法上支持这个。
Java 6或者以前的版本只能靠 interface + anonymous class 来实现。
若是做过 functional programming（比如haskell），应该对 Lamdba 表达
式比较熟悉。
从C++的角度来看，就是 function pointer，但是它是 Strongly Typed。
举例代码来说明。假设要对二叉树遍历，代码很好写，比如：
void inOrder(Tree tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.println(tree.getValue());
inOrder(tree.getRight());
}
}
但是如上的函数只是把Node的值打印到终端。若是要变得generic一点，要遍历的
过程中，能引入一个函数，对每一个Node执行这个函数，该多好。这样就引入了一
个概念：能... 阅读全帖 |
|
a***r
发帖数: 93 | 15 这题如果用DP来做，哪位给分析一下什么是subproblem？
【 以下文字转载自 Programming 讨论区 】
发信人: minisand (老婆是A+海博), 信区: Programming
标 题: 请教一个字符串比较排序的问题
发信站: BBS 未名空间站 (Mon Nov 9 16:35:46 2009, 美东)
之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
... 阅读全帖 |
|
q*********u
发帖数: 280 | 16 【 以下文字转载自 JobHunting 讨论区 】
发信人: yinyueyouge (隐约有歌), 信区: JobHunting
标 题: Re: java enclosure是什么-今天被hm问倒了
发信站: BBS 未名空间站 (Fri Oct 22 09:27:57 2010, 美东)
感觉对方是在问 Closure。
这个是 Java 对 Lambda 表达式的实现。Java 7 已经确定在语法上支持这个。
Java 6或者以前的版本只能靠 interface + anonymous class 来实现。
若是做过 functional programming（比如haskell），应该对 Lamdba 表达
式比较熟悉。
从C++的角度来看，就是 function pointer，但是它是 Strongly Typed。
举例代码来说明。假设要对二叉树遍历，代码很好写，比如：
void inOrder(Tree tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.p... 阅读全帖 |
|
m******d
发帖数: 414 | 17 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
int max = 0;
int index = -1;
for (int i=0; i < length - 1; i++)
{
int c = 0;
while (substrings[i][c] && substrings[i+1][c] && substrings[i][c] ==
substrin... 阅读全帖 |
|
n**********2
发帖数: 648 | 18 qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs) |
|
n**********2
发帖数: 648 | 19 qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs) |
|
d****n
发帖数: 1637 | 20 haskell like version:
def qsort(L):
if len(L) <= 1: return L
return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + \
qsort([ge for ge in L[1:] if ge >= L[0]]) |
|
n****1
发帖数: 1136 | 21 1. 实践中qsort通常是表现非常好的, 我不觉得worst case O(n^2)有啥大不了的.
2. 我举qsort最关键在于提出了并行的可能性, 从而否定必须强耦合这个假设.
3. 肯定有比qsort更适合上mapreduce的方案, 好像有个terasort就很适合hadoop.
4. sort和寻找座位空隙还不是完全对应, 要思考的还有很多. 我是希望抛砖引玉, 不
是给终极方案. 这里面的水很深的. |
|
n*w
发帖数: 3393 | 22 F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger |
|
n*w
发帖数: 3393 | 23 F#:
let rec qsort = function
| [] -> []
| x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
qsort smaller @ [x] @ qsort larger |
|
r****o
发帖数: 1950 | 24 CLRS里面关于Qsort的伪代码提到了在partition之前先取一随机元素和最后一个元素互
换，
如果Qsort是这样实现的话，是不是就跟逆序顺序无序没啥关系了? |
|
g*****e
发帖数: 282 | 25 lgN是指平均complicity，O(N)是最坏情况。这个与Qsort同理。是个经典算法题，类似
qsort的操作就可以了。
怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？ |
|
x***n
发帖数: 70 | 26 Q3:qsort的话，每次从数组中取新的节点插入到待sort的数组应该怎么做呢？我想它还
可以用red-
black tree来做吧，这样插入时间复杂度为lgk,和lz的方法一样，整个的时间复杂度仍
为O(nlgk)
另外，counting sort好像不可以吧？并没有说这个数组中存放的是integer啊。
for
qsort. |
|
f*******t
发帖数: 7549 | 27 这个不是qsort的基础吗，多写几遍qsort就行了。。 |
|
v***a
发帖数: 365 | 28 来自主题: JobHunting版 - 问个算法题 第一次写 c 程序，不保证正确，请自己 debug
程序假设单词是 a to z 组成
用的 bst counting, 然后 导出来 qsort
#include
#include
struct _node;
typedef struct _node {
int cc;
char c;
struct _node * n[26];
struct _node * fa;
} node;
void addToTree(node * root, node * r, const char * p1, const char * p2) {
int t;
int i;
if (p1 == p2) {
if (r->cc == 0) root->cc++;
r->cc++;
return;
}
t = (*p1) - (int)'a';
if (r->n[t] == NULL) {
r->n[t] = (node *... 阅读全帖 |
|
h**********l
发帖数: 6342 | 29 qsort最差还o（n)呢
你说qsort没优势？ |
|
r**********g
发帖数: 22734 | 30 quick sort是O(n^2)好吧。要O(nlogn)，需要先randomize。quick sort还不是stable
的。以前说qsort快主要是cache line优化得好，如果是sort object的话其实都是一样
，我试过，用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
除对象的sorted heap对象。而现在大规模parallel，像MapReduce，其实MergeSort要
好得多。 |
|
h**o
发帖数: 548 | 31 Hi,
qsort： nlogn = log n^n
heapsort：sum(log(i)) = log (n!) < log n^n
为什么 qsort 常数因子最小最优那？ |
|
y*********e
发帖数: 518 | 32 Hashtable查询开支：
- 最好是O(1)
- 最差是O(N)
- 平均是O(1)
对于这个问题，要把输入的数字过一遍，所以用hashtable是最好的。
那个面试官说hash有collision，你应该回复他说这个是最差的情况，但是平均下来
hash查询的复杂度是O(1)。打个比方，qsort最差是O(N^2)，这并不阻碍qsort成为最好
的排序算法之一。 |
|
P****a
发帖数: 864 | 33 他说的那个有点扯了，不过我看过一个说一般机器开发用qsort多，
因为cache结合的好大多数常数比较低的nlgn
而手机用heap sort多因为cpu没那么多cache给qsort发挥优势。而且手机开发尽量少
merge sort因为extra ram资源紧缺 |
|
b*********n
发帖数: 1258 | 34 要解决的问题就是c++ qsort的comparator函数
int comparator ( const void * elem1, const void * elem2 );
comparator已经定义好了
但是我写的这个comparator函数里面还要用到一个第三方的变量
不知道这个问题怎么解决？
我现在的方法是global variable,但是不想用global
或者自己从新写qsort,不过这个工作量太大
不知道有没有什么小trick可以解决这个问题
谢谢 |
|
t*********n
发帖数: 278 | 35 the sample from programming pearls. But, I got complier error at this line
qsort(a, n, sizeof(char *), pstrcmp). How can I fix this one? Thanx.
#include
#include
#include
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
#define MAXN 5000000
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
} |
|
r*********r
发帖数: 3195 | 36 the new c compiler is stricter on type checking.
the last argument to qsort function is of type:
int ( * comparator ) ( const void *, const void * )
therefore, you need to cast the pstrcmp to this type. do:
typedef int(*cmp_ptr) (const void *, const void *);
qsort(a, n, sizeof(char *), (cmp_ptr) pstrcmp); |
|
S*********g
发帖数: 5298 | 37 不需要qsort， merge sort都比qsort强 |
|
t****t
发帖数: 6806 | 38 qsort is not a part of STL. STL is standard template library. qsort is not
template... |
|
n****1
发帖数: 1136 | 39
你这样搞, 离socket buffer overflow只有一步之遥啊. 也许你们搞trading的整天承
受风险已经惯了, 觉得这个没啥问题, 可首长不同意啊. 你的performance per dollar
再高人家也不买帐的.
n值小的话qsort未必最好,但一列车有一两千个座位, 一秒钟有几百万个request, 单机
很玄. 我还是宁可牺牲性能, 也要上并行保证稳定性的. qsort的并行版就是现在很火
的mapreduce. 这样我就可以只专注于算法/逻辑,不用重造轮子, 也不用担心
consistency/availability.
我的见识是挺浅薄的, 也没35岁, 你要鄙视我就鄙视好了. |
|
d****i
发帖数: 4809 | 40 Plain old vanilla pure C code. Disclaimer: copied from online
#include
#include
static void swap(void *x, void *y, size_t l) {
char *a = x, *b = y, c;
while(l--) {
c = *a;
*a++ = *b;
*b++ = c;
}
}
static void sort(char *array, size_t size, int (*cmp)(void*,void*), int
begin, int end) {
if (end > begin) {
void *pivot = array + begin;
int l = begin + size;
int r = end;
while(l < r) {
if (cmp(array+l,pivot) <= 0) {
... 阅读全帖 |
|
a*****e
发帖数: 1700 | 41 我很久以前写的，看看是否难懂 20 倍？
请自动忽略里面的 fork，当时是做了个 lightweight thread scheduler 拿快排做测
试。
> qsortM = qsort (i j a -> sysio $ qsplit i j a) fork
> qsort split fork (i, j) arr = aux (i, j)
> where
> aux (i, j) =
> if j <= i then return () else do
> k <- split i j arr
> if j - i > 10000 then (fork $ aux (i, k - 1)) >> return ()
> else aux (i, k - 1)
> aux (k + 1, j)
> qsplit left right arr = do
> v <- readArray arr right
> let split' i j = if j... 阅读全帖 |
|
b*****t
发帖数: 840 | 42 写不出来qsort不一定是什么问题，这里有区别
工业经验长的反而不一定记得qsort的算法过程，是有可能的，没有大问题，看一下
spec能写出就行
但是如果知道大概的算法，但无能力转化成code，那就不要滥竽充数了，太差
数学所用的思维和programming至少有些部分是mutually exclusive
不少数学系的很牛人，写个matlab都费劲，手把手教了这个，换个algo又趴下了，就是
没有那个代码表达能力，见得太多了 |
|
w**a
发帖数: 1024 | 43 这样行不？
假设所有元素都是非负（如果有负的,一下算法也很容易修补）
先把所有列归一化 n^2
然后对第一行qsort,找到横向连续相同的那些column index section。
一个index section 定义为：
若第2,3,4列数值相同，就把[2,3,4]定义为一个index section.
显然，这些sections应该是disjoint continuous sections，很容易找到。
对这些cont. sections随机抽出一行再进行qsort，
如此反复 上6，7次后如果你觉得差不多了（这里面有个概率，应该<1%的概率，在6,7次
后都相同）。整个列进行比较。
whether |
|
J********a
发帖数: 5208 | 44 说白了，图灵，诺依曼不会红黑树，不会图算法，不会qsort，不会FFT，不会dp，是不
是要说哥几个都是计算机盲啊？除了搞理论计算机的都不是CS? |
|
c****3
发帖数: 10787 | 45 基本的逻辑学我们还是学过的。你说的逻辑上不能证明进化论的自然选择过程。
而且DNA其实和程序代码是类似的，程序代码或者模块，如果被重用，你能说这两个程
序是共同祖先吗。一个程序代码上百万，大家都用了同样的qsort，这几十行代码，所
以这两个程序是共同祖先，推理过程，逻辑上合理吗？ |
|
s*****e
发帖数: 16824 | 46 qsort如果实现很相似，尤其是连comment 都相似的话，确实有理由认为是从同一个祖
先改过来的。而如果两个软件，有成千上万个函数，其中百分之八十都出现类似的相似
，那几乎可以铁板钉钉的说两者是源出同一个祖先的。生物上就是这样的情况。 |
|
s******r
发帖数: 2876 | 47 c不是自带qsort吗？
我用c写过一个 从文件中读取 一百万个数字 用quicksort 排序的 你要要的话 私信我
我可以发给你 你改改就可以用 |
|
|
|
|
