当前在线人数18312
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:靠。Sedgewick这3w-qsort算法居然还有bug!
[同主题阅读] [版面: 葵花宝典] [作者:adven] , 2005年01月07日00:19:30
adven
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: adven (冒险者), 信区: Programming
标  题: 靠。Sedgewick这3w-qsort算法居然还有bug!
发信站: Unknown Space - 未名空间 (Fri Jan  7 01:43:23 2005), 转信

http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf

第9页算法,递归前面那两行,居然把 k<=p, k>=q 给漏了!
虽然结果依然正确,且不影响主要performance,但明显是个bug嘛:)

void quicksort(Item a[], int l, int r)
{
  int i = l-1, j = r, p = l-1, q = r; Item v = a[r];
  if (r <= l) return;
  for (;;)
    {
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
        if (a[i] == v) { p++; exch(a[p], a[i]); }
        if (v == a[j]) { q--; exch(a[j], a[q]); }
    }
  exch(a[i], a[r]); j = i-1; i = i+1;
  for (k = l; k < p; k++, j--) exch(a[k], a[j]);
  for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
  quicksort(a, l, j);
  quicksort(a, i, r);
}

--

        理论联系实际

--
※ 修改:.adven 于 Jan  7 01:58:56 修改本文.[FROM: 199.74.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 199.74.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996