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; 
  }
}