注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2014.12.21 quick sort summary  

2014-12-21 12:31:33|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
The following code or text were extracted from Algorithms 4th.

public class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a); // Eliminate dependence on input.
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi); // Partition (see page 291).
        sort(a, lo, j-1); // Sort left part a[lo .. j-1].
        sort(a, j+1, hi); // Sort right part a[j+1 .. hi].
    }
}

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].
}

Improvement:
Cutoff to insertion sort. As with most recursive algorithms, an easy way to improve
the performance of quicksort is based on the following two observations:
■ Quicksort is slower than insertion sort for tiny subarrays.
■ Being recursive, quicksort’s sort() is certain to call itself for tiny subarrays.
Accordingly, it pays to switch to insertion sort for tiny subarrays. A simple change to
Algorithm 2.5 accomplishes this improvement: replace the statement
    if (hi <= lo) return;
in sort() with a statement that invokes insertion sort for small subarrays:
    if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; }
The optimum value of the cutoff M is system-dependent, but any value between 5 and
15 is likely to work well in most situations (see Exercise 2.3.25).

Median-of-three partitioning. A second easy way to improve the performance of
quicksort is to use the median of a small sample of items taken from the subarray as the
partitioning item. Doing so will give a slightly better partition, but at the cost of computing
the median. It turns out that most of the available improvement comes from
choosing a sample of size 3 and then partitioning on the middle item (see Exercises
2.3.18 and 2.3.19). As a bonus, we can use the sample items as sentinels at the ends of
the array and remove both array bounds tests in partition().

Entropy-optimal sorting. Arrays with large numbers of duplicate keys arise frequently
in applications. For example, we might wish to sort a large personnel file
by year of birth, or perhaps to separate females from males. In such situations, the
quicksort implementation that we have considered has acceptable performance,
but it can be substantially improved. For example, a subarray that consists solely of
items that are equal (just one key value) does not need to be processed further, but
our implementation keeps partitioning down to small subarrays. In a situation where
there are large numbers of duplicate keys in the input array, the recursive nature of
quicksort ensures that subarrays consisting solely of items with keys that are equal will
occur often. There is potential for significant improvement, from the linearithmic-time
performance of the implementations seen so far to linear-time performance.

The following is a c implementation:
#include "stdafx.h"

#include <stdlib.h>
#include <stdio.h>

int * g_array = NULL;
int g_array_len = 0;

void output()
{
int i = 0;
for ( i = 0; i < g_array_len; ++i ) {
printf( "%d ", g_array[i] );
}

printf( "\n" );
}

void exg( int * p_array, int x, int y )
{
p_array[x] = p_array[x] ^ p_array[y];
p_array[y] = p_array[x] ^ p_array[y];
p_array[x] = p_array[x] ^ p_array[y];
}

int partition( int * p_array, int lo, int hi )
{
int i = lo;
int j = hi - 1;
int pivot = p_array[hi];

while ( 1 ) {
while ( p_array[i] < pivot ) ++i;
while ( p_array[j] >= pivot ) --j;
if ( i >= j ) {
break;
}

exg( p_array, i, j );
}

if ( i != hi ) {
exg( p_array, i, hi );
}

output();
return i;
}

void sort( int * p_array, int lo, int hi )
{
int i = 0;

if ( lo >= hi ) {
return;
}

i = partition( p_array, lo, hi );

if ( lo < (i - 1) ) {
sort( p_array, lo, i - 1 );
}

if ( hi > (i + 1) ) {
sort( p_array, i + 1, hi );
}
}

void quick_sort( int * p_array, int array_len )
{
sort( p_array, 0, array_len - 1 );
}

int main(int argc, char* argv[])
{
int i = 0;

scanf_s( "%d\n", &g_array_len );
g_array = (int *) malloc( sizeof(int)*g_array_len );

if ( g_array ) {
for ( i = 0; i < g_array_len; ++i ) {
scanf_s( "%d", &g_array[i] );
}

quick_sort( g_array, g_array_len );

free( g_array );
} else {
printf("Failed to allocate memory\n");
}

return 0;
}

  评论这张
 
阅读(266)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017