2015
04-13

# Indeed Quick Sort

Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O (nlogn) comparisons to sort n items in list T.
Given a list T, the steps are as follows:
1. Randomly pick an element X in list T, called a pivot.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sorts the sub-list of lesser elements and the sub-list of greater elements.
Here we define the cost C of sorting list T to be the sum of the following three parts:
1. The number of elements greater than X on X’s left.
2. The number of elements lesser than X on X’s right.
3. The cost of recursively sorting the sub-lists.
Could you please tell me what is the expected value of the cost C?

There are multiple test cases. In each test case, the integer N (N<=15000) in the first line gives the number of elements, followed by N integers in the second line describing the elements in the list.

There are multiple test cases. In each test case, the integer N (N<=15000) in the first line gives the number of elements, followed by N integers in the second line describing the elements in the list.

3
1 2 3

0.000000

1. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。