algorithm - Does quicksort perform data movement within its inner loops? - Stack Overflow

admin管理员组

文章数量:1201187

I'm reading Sedgewick's Algorithms, 4th edition that has the following excerpt:

The inner loop of quicksort (in the partitioning method) increments an index and compares an array entry against a fixed value. This simplicity is one factor that makes quicksort quick: it is hard to envision a shorter inner loop in a sorting algorithm. For example, mergesort and shellsort are typically slower than quicksort because they also do data movement within their inner loops.

However, from the implementation of quicksort, I can already see that its inner loops also move data by exchanging the items that are out of place. In the following code block, the calls to exch() method do just that:

private static int partition(Comparable[] a, int lo, int hi) { // Partition into a[lo..i-1], a[i], a[i+1..hi].
    int i = lo, j = hi + 1; // left and right scan indices
    Comparable v = a[lo]; // partitioning item
    while (true) { // Scan right, scan left, check for scan complete, and exchange.
        while (less(a[++i], v))
            if (i == hi)
                break;
        while (less(v, a[--j]))
            if (j == lo)
                break;
        if (i >= j)
            break;
        exch(a, i, j);
    }
    exch(a, lo, j); // Put v = a[j] into position
    return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}

So, does the quicksort algorithm perform data movement within its inner loops? If yes, then what does the author mean when asserting that quicksort is more efficient compared to other sorts (mergesort and shellsort) on the basis of data movements within the inner loops?

本文标签： algorithmDoes quicksort perform data movement within its inner loopsStack Overflow