summaryrefslogtreecommitdiff
path: root/cesar/lib/heapsort.h
blob: 33313b88055129c7d8d5e238aee128d331e22ed1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#ifndef LIB_HEAPSORT_H_
#define LIB_HEAPSORT_H_

/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/heapsort.h
 * \brief   heapsort algorithm.
 * \ingroup lib
 * 
 * Sort an array of randomed value using a virtual heap (it does not create
 * an real heap in the memory).
 *
 * see the heapsort page on wikipedia
 * http://en.wikipedia.org/wiki/Heapsort
 *  
 * Complexity : O (n log n)
 * Mem : O (1)
 * 
 * Some MACROS must be defined to use the heapsort.
 * 
 * LIB_HEAPSORT_USER_TYPE corresponding to the type the lib heapsort will use
 *  to sort the array
 * 
 * LIB_HEAPSORT_USER_COMP user function to compare two values.
 * LIB_HEAPSORT_USER_SWAP user function swap to exchange two values.
 * 
 * LIB_HEAPSORT_USER_PREFIX user prefix function.
 */

/** Verify if the MACROS had been defined. */
#if (!defined (LIB_HEAPSORT_USER_TYPE) \
    || !defined (LIB_HEAPSORT_USER_COMP_LESSER) \
    || !defined (LIB_HEAPSORT_USER_SWAP) \
    || !defined (LIB_HEAPSORT_USER_PREFIX))
#error "Some macros had not been defined"
#endif

#define lib_heapsort_siftdown PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _siftdown)
#define lib_heapsort_heapify PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _heapify)
#define lib_heapsort PASTE_EXPAND (LIB_HEAPSORT_USER_PREFIX, _heapsort)

/**
 * siftdown the heap.
 * 
 * \param  user_type  the user type to do the siftdown on
 * \param  start  the start position
 * \param  end  the end position
 */
void lib_heapsort_siftdown (LIB_HEAPSORT_USER_TYPE *user_type, uint start, uint end)
{
    uint root;
    uint child;

    dbg_assert (user_type);

    root = start;
    while ((child = root * 2 + 1) <= end)
    {
        if (child < end
        && LIB_HEAPSORT_USER_COMP_LESSER (user_type, child, child + 1))
        {
            child ++;
        }

        if (LIB_HEAPSORT_USER_COMP_LESSER (user_type, root, child))
        {
            LIB_HEAPSORT_USER_SWAP (user_type, root, child);
            root = child;
        }
        else
        {
            break;
        }
    }
}

/**
 * heapify, the user_type to sort
 * 
 * \param  user_type  to sort
 * \param  nb  the number of data in the type
 */
void lib_heapsort_heapify (LIB_HEAPSORT_USER_TYPE *user_type, uint nb)
{
    int start;

    dbg_assert (user_type);
    start = nb / 2 - 1;

    while (start >= 0)
    {
        lib_heapsort_siftdown (user_type, start, nb - 1);
        start --;
    }
}

/**
 * heapsort algorithm
 * 
 * \param  user_type  the data to sort
 * \param  nb  the number of data in the type
 */
void lib_heapsort (LIB_HEAPSORT_USER_TYPE *user_type, uint nb)
{
    dbg_assert (user_type);

    /* Do no sort empty table. */
    if (nb == 0)
        return;

    uint end;
    lib_heapsort_heapify (user_type, nb);

    end = nb - 1;
    while (end)
    {
        LIB_HEAPSORT_USER_SWAP (user_type, 0, end);
        end --;
        lib_heapsort_siftdown (user_type, 0, end);
    }
}

#endif /*LIB_HEAPSORT_H_*/