sort.c

Go to the documentation of this file.

 
#include "user_config.h"
 
#include "sort.h"
 
MEMSPACE
void heapify(int *v, int size, int root)
{
    int largest = root;
    int left  = (root<<1) + 1;
    int right = (root<<1) + 2;
    int tmp;
 
// If left child is larger than root
    if (left < size && v[left] > v[largest])
        largest = left;
 
// If right child is larger than largest so far
    if (right < size && v[right] > v[largest])
        largest = right;
 
// If largest is not root
    if (largest != root)
    {
// swap
        tmp = v[root];
        v[root] = v[largest];
        v[largest] = tmp;
        heapify(v, size, largest);
    }
}
 
 
MEMSPACE
void heapsort(int *v, int size)
{
    int root;
    int tmp;
 
    for(root = size / 2 - 1; root >= 0; --root)
    {
        heapify(v, size, root);
    }
 
// One by one extract an element from heap
    for (root=size-1; root>=0; --root)
    {
// swap
        tmp = v[0];
        v[0] = v[root];
        v[root] = tmp;
        heapify(v, root, 0);
    }
}
 
 
MEMSPACE
void insert_sort(uint16_t *v, int size)
{
    int i,j;
    uint16_t tmp;
 
    for (i = 1; i < size; ++i)
    {
        tmp = v[i];
        for (j = i; j >= 1 && tmp < v[j - 1]; --j)
            v[j] = v[j - 1];
        v[j] = tmp;
    }
}