如何证明均匀分区是快速排序算法的最佳案例? [英] How to prove the evenly partition is the best case for quick sort algorithm?

问题描述

为什么我们说快速排序的最佳情况是每次执行分区时，我们会将列表分为几乎相等的两个部分"?以及如何证明这正是所谓的最佳案例"?

Why we say the bestcase for quicksort is that "each time we perform a partition we divide the list into two nearly equal pieces"? And how to prove this is exactly the so called "best case"?

推荐答案

我创建了一个程序，而不是尝试进行分析.我比较了1/2、1/2(50％50％)分割与1/4、3/4(25％75％)分割的情况，随着n变大，似乎要多花22％的运算.代码设置为1/4,3/4分割:对于1/2,1/2分割，将行从左=(n + 3)/4更改为左=(n + 1)/2.向上舍入的目的是确保left> = 1，以避免无限递归.

I created a program rather than trying to do an analysis. I compared the case of 1/2, 1/2 (50% 50%) split versus 1/4, 3/4 (25% 75%) split, which appears to approach taking 22% more operations as n becomes large. The code is set for the 1/4,3/4 split: for 1/2,1/2 split, change the line from left = (n+3)/4 to left = (n+1)/2. The point of rounding left up is to make sure left >= 1, to avoid infinite recursion.

#include <stdio.h>
typedef unsigned long long uint64_t;
static uint64_t sum;

void qsa(uint64_t n)
{
uint64_t left, right;
    if(n < 2)
        return;
    sum += n;
    left = (n+3)/4;         /* or left = (n+1)/2  */
    right = n - left;
    qsa(left);
    qsa(right);
}

int main()
{
    qsa(1024*1024);
    printf("%llu\n", sum);
    return(0);
}

结果

n = 1024*1024
20971520     1/2 1/2   n log2(n)
25331387     1/4 3/4   ~1.208 n log2(n)

n = 16*1024*1024

402653184    1/2 1/2   n log2(n)
488049677    1/4 3/4   ~1.212 n log2(n)

n = 1024*1024*1024

32212254720  1/2 1/2   n log2(n)
39180282211  1/4 3/4   ~1.216 n log2(n)

n = 16*1024*1024*1024

584115552256 1/2 1/2   n log2(n)
711608157825 1/4 3/4   ~1.218 n log2(n)

这篇关于如何证明均匀分区是快速排序算法的最佳案例?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！