A naive version of QuickSort

marveloustau

1. QuickSort[lis_List] :=
   
2. Join[QuickSort[Select[lis, # < (a = RandomChoice[lis]) &]], {a},
   
3.   QuickSort[Select[lis, # > a &]]]
   
4. QuickSort[{}] := {}

复制代码

比自带的Sort几乎慢了100倍……看还有哪里能够提高一下？

FreddyMusic

he he isn't a classic problem,

Read " OReilly,.Beautiful.Code.(2007).by Andy Oram, Greg Wilson"

3. The Most Beautiful Code I Never Wrote --- Jon Bentley

marveloustau

看过了……我不知道伪代码中的swap是不是一个标准过程，但是Mathematica中似乎并没有提供一个swap的命令。倒是用Rule Substitution可以写成{prev___, a_, midd___, b_, succ___}->{prev, b, midd, a, succ}来完成交换，但是据Wolfram内部人士称这种代换效率挺低的……

我想过前面用了一个Select，后面直接求个补集就行，但是用了Complement却得不到结果。

FreddyMusic

I don't develop the funtion and computer fundamental works.

In my opinion, use the function which has already well builded.

FreddyMusic

One question:

What is difference between " QuickSort[lis_List] :=  "  and "QuickSort[lis_] := " ?

marveloustau

Without "List" specified, the "lis" can be anything, e.g. a single symbol.

The question is, sometimes the built-in functions cannot meet some advanced requirements. We can only do it ourselves.

FreddyMusic

Thanks, i notice that in syntax. I agree with your variable defination, that's more precision.

Anyway, what kind of advanced requirement, you want to realized with Sort ?

marveloustau

应该说不大可能。Mastering Mathematica上面写着说基本上实现相同功能的用户定义函数至少比built-in函数慢十倍以上。

但是有些问题，比如动态规划。还有比如一道Project Euler上面的题目，把一个长度为n的字符串的所有排列按照字典序排列，然后求第m个排列是啥情况。虽然Mathematica提供了一个Permutation，还有Combinatorica里的Permute，但是它们排列的顺序并不是字典序。虽说Sort对字符串排序会按照字典序排列，但是全排列有n!种情况，枚举肯定不现实，所以只能用自己写的。

FreddyMusic

I think there are not available function that you can using exactly as your wish, but you can modifed that and using the core.

However, as a commercial company they would not release every initial code on user documentation.

marveloustau

是呀，我原来还有混进Wolfram把代码和文档偷出来的冲动。

之前有本叫做Power Programming with Mathematica的书，专门讲怎么只用Kernel编程的方法。其实现在的Mathematica 6里好多可以直接用的函数并不是严格意义上的built-in函数，它们其实是独立的package，只不过是启动的时候直接加载了而已。如果是在那个MathKernel程序里它们就用不了。

顺便问下，你那里能找到这本书不？

FreddyMusic

I didn't heard about that book.

gotit

marveloustau 发表于 2008-10-30 14:33
是呀，我原来还有混进Wolfram把代码和文档偷出来的冲动。

之前有本叫做Power Programming with Mathematic ...

这本书已经有电子版了。
http://mathematica.stackexchange ... mming-with-mathemat